Problem overview
isSubtree(root, subRoot) receives the roots of two binary trees and returns true when some node of root, together with all of its descendants, forms exactly the tree subRoot: the same shape and the same value in every place. A tree counts as a subtree of itself. The lesson provides the TreeNode function, whose nodes have val, left and right, with null for a missing child.
In the first example, root = [3,4,5,1,2] and subRoot = [4,1,2]. The node 4 of root has the children 1 and 2 and nothing else below, so it matches and the answer is true. In the second example, root = [3,4,5,1,2,null,null,null,null,0]: now the 2 has a child 0, which subRoot doesn't have, so no node matches and the answer is false. Taking only part of a node's descendants is not allowed.
Approach: try every node, compare the trees
There are two separate questions here. First, are two given trees identical? Second, which node of root should be compared with subRoot? The answer to the second is "every one of them", so the solution asks the first question at each node.
Comparing two trees is a simple recursion: both empty means the same, only one empty means different, different values mean different, and otherwise both pairs of children must be 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, because it can't go deeper than subRoot does without hitting a difference. It is started once per node of root, so the total is O(n · m), which is the budget the lesson sets.
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 also ends the recursion when it steps past a leaf. - Compare at this node. If
isSameTree(root, subRoot)is true, returntrueright away. - Look lower down. Otherwise
subRootmay start in the left subtree or in the right one, so return the two recursiveisSubtreecalls joined with||. Together with the check above, every node ofrootgets tried. - Write the helper
isSameTree(p, q). - Both empty: if
!p && !q, returntrue. Two empty trees are the same tree, and this is where the recursion ends when both sides run past a leaf together. - Only one empty: if
!p || !q, returnfalse. Both being empty has already returned, so exactly one is missing and the shapes differ. - Different values: if
p.val != q.val, returnfalse. Both nodes exist here, so readingvalis safe. - Recurse on both pairs of children and join the results with
&&. The roots match, so the trees are the same exactly when the left subtrees are the same and the right subtrees are the same.
The solution in JavaScript
class Solution {
isSameTree(p, q) {
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, subRoot) {
if (!root) {
return false;
}
if (this.isSameTree(root, subRoot)) {
return true;
}
return this.isSubtree(root.left, subRoot) || this.isSubtree(root.right, subRoot);
}
}
A few details are worth noticing:
- Methods call each other through
this. Inside a class,isSubtreereaches the helper asthis.isSameTree(...). A bareisSameTree(...)would look for a function in the surrounding scope and fail. !ptests fornull. A node is an object, so it is truthy, whilenullis falsy. Here the only falsy values that can appear arenull.- Short-circuiting.
&&skips the right pair when the left pair already differs, and||skips the right subtree ofrootwhen the left one already containssubRoot. !=works on numbers here, but!==is the safer habit in your own code, because!=converts types before comparing.
Complexity
Time: O(n · m). isSubtree visits each of the n nodes of root at most once, and at each one isSameTree compares at most m node pairs.
Space: O(h), where h is the larger depth involved. The recursion depth is bounded by the depth of root for the search, plus at most the depth of subRoot for a comparison. The lesson limits trees to 400 levels, which is well within JavaScript's call stack.
Edge cases and common mistakes
- Matching only the root's value. For
root = [1,1]andsubRoot = [1], the top node 1 has a child, so the tree under it is notsubRoot. The answer is stilltrue, because the left child 1 has nothing below it. Checking values without checking that both sides end at the same place gives wrong answers. - Ignoring extra descendants. A node that matches
subRootat the top but has more nodes below is not a match. This is whyisSameTreemust compare thenullchildren too. - Forgetting the empty-tree check in
isSubtree. Without it, the recursion runs past a leaf and reads.leftofnull, which throws aTypeError. - Swapped order of the two checks in
isSameTree. Readingp.valbefore testing fornullthrows the same error. - Same shape, different values. A tree that is a mirror image or has the right shape with other numbers must not match.
Testing
With trees written in level order, the solution returns:
root = [3,4,5,1,2],subRoot = [4,1,2]givestrue.root = [3,4,5,1,2,null,null,null,null,0],subRoot = [4,1,2]givesfalse.root = [1,1],subRoot = [1]givestrue.root = [1,2],subRoot = [2]givestrue.root = [1,null,2],subRoot = [1]givesfalse.root = [1,2,3],subRoot = [3,4]givesfalse.
