Problem overview
isSubtree receives two binary trees, root and subRoot, and returns a Boolean: true when some node of root, together with all of its descendants, forms exactly the same tree as subRoot. Same means the same shape and the same value in every place. A tree counts as a subtree of itself. The lesson provides the TreeNode class: each node has a value and two fields, left and right, which are null when a child is missing.
With root = [3,4,5,1,2] and subRoot = [4,1,2], the node 4 of root has the children 1 and 2, which is exactly subRoot, so the answer is true. If the 2 in root also had a child 0, as in [3,4,5,1,2,null,null,null,null,0], the answer would be false: a subtree takes every descendant of its node, and subRoot has no 0. For root = [1,1] and subRoot = [1] the answer is true. The root 1 has a child, so the tree under it is not subRoot, but its left child has nothing below it and matches.
Approach: compare at every node
The note asks for O(n · m) time, where n and m are the numbers of nodes in root and subRoot. The idea has two parts.
- A helper,
isSameTree, answers whether two trees are identical. It walks both trees in step and stops at the first difference. isSubtreecalls that helper at the top ofroot, and if it fails, tries again at the left child and at the right child, and so on down the tree.
Each comparison stops after at most m nodes: it can't go deeper than subRoot does, because once subRoot runs out, the two sides differ and the answer is false. One comparison is started at each of the n nodes of root, so the total is O(n · m).
Step by step
The lesson writes isSubtree first, assuming the helper exists, and then the helper.
- Base case for the search. If
rootisnull, returnfalse. An empty tree has no node wheresubRootcould start, andsubRootalways has at least one node. This check also ends the recursion when it steps below a leaf. - Try the current node. If
isSameTree(root, subRoot)is true,subRootstarts here, so returntrue. - Try lower down. Otherwise return
isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot). Together with step 2, this tries every node ofrootas the starting point. The||operator skips the right side when the left side already found a match. - Write the helper's signature.
isSameTreetakes twoTreeNodeparameters,pandq, and returns aBoolean. - Both empty. If
p == null && q == null, returntrue: two empty trees are the same. This is how the recursion ends when both trees run out at the same time. - Only one empty. If
p == null || q == null, returnfalse. Both being empty was handled above, so exactly one tree is empty and the shapes differ. - Different values. If
p.value != q.value, returnfalse. Both nodes exist now, so reading their values is 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:
isSameTree(p.left, q.left) && isSameTree(p.right, q.right).
The solution in Scala
class Solution {
def isSameTree(p: TreeNode, q: TreeNode): Boolean = {
if (p == null && q == null) {
return true
}
if (p == null || q == null) {
return false
}
if (p.value != q.value) {
return false
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}
def isSubtree(root: TreeNode, subRoot: TreeNode): Boolean = {
if (root == null) {
return false
}
if (isSameTree(root, subRoot)) {
return true
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
}
}
Scala details worth knowing:
- The order of the checks matters. The two
nullchecks come beforep.valueis read. Reading a field ofnullthrows aNullPointerException, so the value comparison is only safe once both nodes are known to exist. ==andnull.p == nullis a normal comparison in Scala and is safe even whenpisnull. Only reading a field or calling a method onnullfails.- Short-circuit operators.
&&and||evaluate their right side only when needed. That is what lets a comparison stop at the first difference and the search stop at the first match. - Methods can call each other in any order. Inside a class,
isSubtreecan useisSameTreewhether it is written above or below it. The explicit result types,Boolean, are required on these methods because they call themselves recursively. return. The last expression of a block is its value in Scala, soreturnis often left out, but it works here to leave the method early, and it keeps each case on its own line.
Complexity
Time: O(n · m). isSubtree visits each of the n nodes of root once and starts one isSameTree call at each. A comparison visits at most m nodes of subRoot, plus the empty places just below them, which is still O(m). In most trees, mismatches are found early and the work is much smaller, but the worst case, a tall chain of equal values, reaches the bound.
Space: O(h), where h is the height of root. The recursion needs one call frame per level, and the lesson limits the trees to 400 levels, which the JVM's call stack handles easily.
Edge cases and common mistakes
- Checking only the root. Comparing
rootwithsubRootand nothing else misses every match lower down. Withroot = [1,2]andsubRoot = [2]the answer istrue, but only because the search goes down to the left child. - Matching values instead of whole subtrees. Finding a node with the same value as
subRoot's root is not enough. The tree under it must match completely, including the places where a child is missing. That is why the helper treatsnullagainst a real node as a difference. - A match that is too small. With
root = [1,2]andsubRoot = [1]the answer isfalse: the root has a child, so the tree under it is not a single node, and no other node holds a 1. - Shapes that look alike.
[1,null,2]and[1,2]hold the same values but differ in which side the 2 hangs on. Comparingleftwithleftandrightwithrightkeeps them apart. - A tree is a subtree of itself.
root = [5]andsubRoot = [5]givestrue; the check at the top ofrootfinds it.
Testing
These results come from running the solution above on each input:
| 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,2] | [2] | true |
[1,2] | [1] | false |
[1,null,2] | [2] | true |
[1,2,3] | [3,4] | false |
[5] | [5] | true |
