Problem overview
isSubtree receives the roots of two binary trees, root and subRoot, and returns true when subRoot appears inside root. "Appears" has a strict meaning here: some node of root, taken together with all of its descendants, must have exactly the same shape and the same values as subRoot. A tree counts as a subtree of itself.
With root = [3,4,5,1,2] and subRoot = [4,1,2], the node 4 and its children 1 and 2 match subRoot, so the result is true. If the 2 also had a child 0, the result would be false: a subtree takes every descendant of its node, so no node of root would give exactly [4,1,2].
The lesson provides the TreeNode class, with val, left and right fields. An absent child is null.
Approach: compare at every node
The question splits into two smaller ones. First, are two trees identical? Second, which node of root should be compared with subRoot? We don't know where subRoot might start, so we try all of them: the root itself, then everything in the left subtree, then everything in the right subtree.
The identical-trees check is a classic recursion: two trees are the same when their roots hold the same value and their left subtrees and right subtrees are the same. A comparison stops as soon as it finds a difference, and it never looks at more than m nodes, where m is the size of subRoot. It is started at each of the n nodes of root, so the total work is O(n · m). That matches the bound in the statement, and with at most 2000 and 1000 nodes it is fast enough.
Step by step
- Base case of the search. If
rootisnull, returnfalse. An empty tree has no node wheresubRootcould start, andsubRoothas at least one node. This check also ends the recursion when the search steps past a leaf. - Try the current node. If
this.isSameTree(root, subRoot)is true, returntrueright away. - Try lower nodes. Otherwise
subRootcan only start somewhere below, so returnthis.isSubtree(root.left, subRoot) || this.isSubtree(root.right, subRoot). The||skips the right side when the left side has already found a match. - Write the helper.
isSameTree(p, q)takes twoTreeNode | nullvalues and returns aboolean. - Both empty. If
!p && !q, the trees are equal, so returntrue. This is also where the recursion stops when both sides run out at the same moment. - Only one empty. If
!p || !q, exactly one of them is empty, because the previous check handled "both". The shapes differ, so returnfalse. - Different values. If
p.val != q.val, returnfalse. Both nodes exist at this point, so readingvalis safe. - Recurse. The roots match, so the trees are the same exactly when the left pair and the right pair of subtrees are:
this.isSameTree(p.left, q.left) && this.isSameTree(p.right, q.right).
The solution in TypeScript
class Solution {
isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (!p && !q) {
return true;
}
if (!p || !q) {
return false;
}
if (p.val != q.val) {
return false;
}
return this.isSameTree(p.left, q.left) && this.isSameTree(p.right, q.right);
}
isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
if (!root) {
return false;
}
if (this.isSameTree(root, subRoot)) {
return true;
}
return this.isSubtree(root.left, subRoot) || this.isSubtree(root.right, subRoot);
}
}
TypeScript details
TreeNode | nullis a union type. Afterif (!p || !q) return false;the compiler's control-flow analysis knows neither isnull, which is whyp.valandq.valare allowed on the next line. These annotations are erased when the code compiles to JavaScript; thenullchecks themselves are what protect you at run time.!pis true fornull. ATreeNodeobject is always truthy, even when itsvalis0, so testing the node rather than its value is safe.- Methods call each other through
this. WritingisSameTree(...)withoutthis.would look for a function outside the class and fail. !=works here because both sides are numbers. In TypeScript code,!==is the usual habit.
Complexity
Time: O(n · m). isSubtree visits each of the n nodes of root once, and each visit calls isSameTree, which compares at most m node pairs because it ends when the smaller tree runs out.
Space: O(h) for the recursion stack, where h is the height of root, plus up to the height of subRoot for the comparison running on top of it. The statement limits depth to 400 levels, which the call stack handles. For a very deep tree the recursion could overflow the stack.
Edge cases and common mistakes
- Matching only the values. Finding a node whose value equals
subRoot.valis not enough. The whole tree below it must match, so a node with an extra descendant is a different tree. - Stopping when
subRootruns out. A version of the comparison that returnstrueoncesubRootis exhausted would accept a node that still has children. In this solution, "one side empty, the other not" returnsfalse. - Forgetting that a tree is a subtree of itself. Step 2 compares at
rootbefore going down, which covers that case. - Checking only the root. Without the two recursive calls in
isSubtree, onlysubRootequal to the whole tree would be found. - Repeated values. With
root = [1,1]andsubRoot = [1], the root 1 fails because it has a child, but its left child is a leaf with value 1 and matches. Trying every node is what makes this work.
Testing
Running the solution on a few trees, written in level order, gives:
root | subRoot | Result |
|---|---|---|
[3,4,5,1,2] | [4,1,2] | true |
[3,4,5,1,2,null,null,null,null,0] | [4,1,2] | false |
[1,1] | [1] | true |
[1] | [1] | true |
[1,2,3] | [3,4] | false |
[1,null,2] | [2] | true |
