Binary Tree Structural Check | Dataford Interview Questions

Algorithm question: determine whether binary tree B is a substructure of binary tree A. Describe your approach first, then implement it.

Asked in the round 1 coding stage.

Input and Output

Represent each tree as [value, left, right], where a missing child is null. Implement is_substructure(a, b) and return true if B matches a connected pattern in A. A pattern may end before A does, but every node in B must match in value and position. An empty B is not a substructure.

Constraints

Each tree contains at most 1000 nodes.
Node values are integers in the range -10^9 to 10^9.
Either input tree may be null.
An empty B is not a valid substructure.

Function Signature

def is_substructure(a, b):

Your question is Binary Tree Structural Check. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem