Subtree of Another Tree
Given the roots of two binary trees, rootsubRootrootsubRootsubRoot
Limits: rootsubRoot
Example 1
Output: true
Explanation: the left child of 3 holds the tree 4 with children 1 and 2.
Example 2
Output: false
Explanation: the 2 under node 4 has a left child 0, while the 2 in subRoot is a leaf.
Example 3
Output: true
Explanation: the root does not match because it has a child, but the lone leaf 1 below it does.
How to Think About It
Step 1: Name the candidates
A subtree is fixed by its top node: pick a node of rootroot
Step 2: Test one candidate with Same Tree
A candidate matches when it and subRoot
Step 3: Try every node with a traversal
The answer is true if the tree rooted at root
Step 4: Why a value match is not the end
Equal top values only make a node worth checking. In Example 3 the root 1 equals the top of subRootsubRoot
Step 5: Why the check needs the ends to agree
Same Tree fails when one side has a child and the other has null
Walkthrough
Example 2, in the order the recursion visits the nodes of root
| Candidate top | Comparison with subRoot | Result |
|---|---|---|
| 3 | 3 vs 4 | values differ: false |
| 4 | 4 vs 4, then 1 vs 1 (both leaves), then 2 vs 2 | 2 has left child 0, subRoot's 2 has none: false |
| 1 | 1 vs 4 | values differ: false |
| 2 | 2 vs 4 | values differ: false |
| 0 | 0 vs 4 | values differ: false |
| 5 | 5 vs 4 | values differ: false |
No candidate matches, so the answer is false. In Example 1 the second row succeeds and the search stops there.
Java Solution
isSubtreerootisSameTreesubRoot
- The base case: when
isroot there is no node left to start from, so the answer is false.null always has at least one node, so an empty spot never matches it.subRoot - Three chances: the
chain tries the current node first, then the left subtree, then the right. It stops at the first true, so Example 1 never visits node 5.|| - The null check in isSameTree:
is true only when both area == b . That is how an extra child on either side, like the 0 in Example 2, ends a match.null - Negative values: values are compared with
on== , so -104 and 104 need no special handling.int contains[-10000, 10000] .[10000]
A common mistake is to stop at the first node whose value equals subRoot.val
public class SubtreeOfAnotherTree {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return false; // ran out of places where subRoot could start
}
return isSameTree(root, subRoot)
|| isSubtree(root.left, subRoot)
|| isSubtree(root.right, subRoot);
}
private boolean isSameTree(TreeNode a, TreeNode b) {
if (a == null || b == null) {
return a == b; // equal only if both are missing
}
return a.val == b.val && isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
}
}
Complexity
- Time: O(m × n), where m and n are the node counts of
androot . Each of the m nodes starts one comparison, and a comparison can walk up to n nodes before it fails. Two chains of equal values, 2000 and 1000 nodes long, with a different last leaf insubRoot , reach this bound.subRoot - Space: O(h1 + h2), where h1 and h2 are the heights of the two trees. The
calls stack up along one path ofisSubtree , and the comparison running on top of them adds at most one frame per level ofroot .subRoot
The inner check on its own is