Problem overview
The method isSubtree receives the roots of two binary trees, root and subRoot, and returns true when subRoot is a subtree of root. A subtree here is a node of root together with all of its descendants. The match must be exact: the same shape and the same value in every place. A tree counts as a subtree of itself.
The lesson provides the TreeNode class, with the fields val, left and right and a constructor that takes the value. A missing child is null.
Take root = [3,4,5,1,2] and subRoot = [4,1,2]. The node 4 in root has the children 1 and 2 and nothing below them, which is exactly subRoot, so the answer is true. Add a node 0 below the 2 and the answer becomes false: the node 4 now has a descendant that subRoot lacks, and no other node of root can match.
Approach: compare at every node
If subRoot appears in root, it starts at some node. So the plan has two parts:
- a way to ask "are the trees that start at these two nodes identical?", which the helper
isSameTreeanswers; - a walk over every node of
rootthat asks that question at each one.
Comparing two trees is a recursion on shape: two empty trees are the same, an empty tree and a non-empty one are different, and two non-empty trees are the same when their roots hold equal values and both pairs of children are the same trees. The walk is a recursion too: subRoot is a subtree of root if it matches at root itself, or if it is a subtree of the left child, or of the right child.
The cost is O(n · m), where n is the number of nodes in root and m the number in subRoot. The walk visits each of the n nodes once, and a comparison can never go beyond the nodes of subRoot: it stops as soon as one side runs out of nodes or the values differ. Faster solutions exist, such as turning both trees into strings and searching one inside the other, but they need a careful encoding. This lesson keeps the direct comparison.
Step by step
- Stop at an empty
root. An empty tree has no node wheresubRootcould begin, andsubRoothas at least one node, so the answer isfalse. This is also what ends the walk after a leaf. - Try the current node. If
isSameTree(root, subRoot)is true, the search is over. - Otherwise search lower down. Recurse into
root.leftandroot.rightwith the samesubRoot, joined with||. If the left side finds it, the right side is skipped. - Write
isSameTree(p, q). Both parameters areTreeNodes and it returnsboolean. - Both
nullmeans the same. Two empty trees are identical, and this is where the comparison stops when both sides end together. - Exactly one
nullmeans different. The both-null case has returned already, so if either isnullhere, the other one is not. - Different values mean different trees. Neither node is
nullat this point, so readingvalis safe. - Compare the children. The roots match, so the trees are the same exactly when the left subtrees are the same and the right subtrees are the same, joined with
&&.
The solution in Java
class Solution {
boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.val != q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return false;
}
if (isSameTree(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
}
Details worth a closer look:
- The order of the checks matters.
p.valon anullreference throws aNullPointerException, so the two null checks come before the value check. The first check handles both-null, which lets the second one,p == null || q == null, mean "exactly one". - Short-circuiting.
&&and||evaluate the right-hand side only when the left one doesn't already decide the result. That saves work, and it never changes the answer here, because neither call has side effects. - Values, not references. The code compares
val, anint, with!=, which is correct for primitives. Comparing the nodes themselves with==would ask whether they are the very same object. Two separately built nodes holding 5 are different objects, soa == bisfalsefor them, whileisSameTree(a, b)istrue. - The helper has no modifier.
isSameTreeis package-private, andisSubtreeis thepublicmethod the tests call. The helper is an instance method, soisSubtreecalls it by name without any prefix.
Complexity
Time: O(n · m). isSubtree reaches each of the n nodes of root at most once, and each visit starts one isSameTree call. That call visits at most m pairs of nodes, since it only moves down while both trees still have nodes, and subRoot has m of them. The worst case is a root full of values that match subRoot's for a long stretch before differing.
Space: O(h), where h is the height of root, for the recursion. The lesson limits the trees to 400 levels, so the recursion depth stays small. A tree shaped like a linked list would make h equal to n, and a much deeper one could overflow the stack.
Edge cases and common mistakes
- A subtree takes every descendant. With
root = [3,4,5,1,2,null,null,null,null,0]andsubRoot = [4,1,2]the result isfalse. Checking only that the node's value and its children match would answertruewrongly. The recursion has to reach the nulls below 1 and 2 to see the extra 0. - Equal values on different levels. For
root = [1,1]andsubRoot = [1]the comparison at the top fails, because the root has a child, but the left child is a leaf holding 1, so the result istrue. This is why the walk continues after a failed comparison. - Same values, different shape.
root = [1,2]andsubRoot = [2,null,3]givesfalse, androot = [1,null,2]withsubRoot = [2,1]also givesfalse: a child on the other side, or in a different place, is a different tree. - Returning after the first failed comparison. Writing
return isSameTree(root, subRoot);alone only tests the top of the tree. - Forgetting the empty-
rootcheck. Without it the recursion walks past the leaves and fails with aNullPointerExceptionwhen it readsroot.leftof a missing node.
Testing
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],subRoot = [1]givestrue.root = [1,2],subRoot = [2,null,3]givesfalse.root = [1,null,2],subRoot = [2,1]givesfalse.
