Subtree of Another Tree
You get the roots of two binary trees, root and subRoot. Return true if there is a node in root whose whole subtree (that node and all of its descendants) is identical to subRoot in shape and in values. Otherwise return false.
The tree root counts as a subtree of itself. Both trees are written in level order, with null for a missing child.
Examples
Input root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
Output true
Input root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]
Output false
The node 2 has an extra child 0 in root.
Input root = [1, 1], subRoot = [1]
Output true
The leaf 1 is a subtree.
Constraints
- 1 <= number of nodes in root <= 200
- 1 <= number of nodes in subRoot <= 100
- -10,000 <= node value <= 10,000
Stuck? Take one hint at a time
Common mistakes
- Checking only the root values and ignoring the rest of the subtree, which accepts a node with extra descendants.
- Leaving out the marker for empty children in the string version, so different shapes give the same string.
- Leaving out the separator before each value, so 12 matches inside 112.
- Calling the same-tree check only at the root of the big tree, instead of at every node.
Questions an interviewer may ask next
- Count how many times subRoot appears in root.
- Return the node where the subtree starts. (The same walk, returning the node.)
- Make the string version fast in the worst case. (Use a linear time search such as KMP, or hash the subtrees.)
- Allow the shape to match but not the values (an unlabeled subtree). Which approach still works?
root
[3,4,5,1,2]
subRoot
[4,1,2]
Expected output
true
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.