Problem overview
The function isSubtree receives the roots of two binary trees, root and subRoot, and returns 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 struct, with the fields Val, Left and Right.
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 below them, which is exactly subRoot, so the answer is true. In the second example, root has an extra node 0 below the 2. The node 4 of root now owns a bigger tree than subRoot, and no other node matches either, so the answer is false. A subtree always takes every descendant of its top node: you can't cut it off early.
In the third example, root = [1,1] and subRoot = [1]. The root 1 has a child, so the tree under it is not subRoot. Its left child 1 has nothing below it, and that tree equals subRoot, so the answer is true.
Approach: compare at every node
The idea splits the problem in two:
- Decide whether two trees are identical. This is a small recursive function,
isSameTree. - Try that comparison with
subRootagainst the tree under every node ofroot.
The statement sets a budget of O(n · m) time, where n is the number of nodes in root and m the number in subRoot. That matches the plan: there are n places to start, and each comparison looks at no more than m nodes, because it stops as soon as one tree runs out of nodes or two values differ. Faster methods exist, such as turning both trees into strings and searching for one inside the other, but this lesson uses the comparison, which needs no extra memory beyond the recursion.
Step by step
- Stop at an empty tree. If
rootisnil, there is no node wheresubRootcould start, andsubRootalways has at least one node. Returnfalse. This also ends the recursion when it steps below a leaf. - Check the tree that starts here. If
isSameTree(root, subRoot)is true, a match has been found, so returntrue. - Look lower down. Otherwise
subRootmay start in the left or the right part, so returnisSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot). Each call repeats the same three steps one level lower, so every node ofrootgets its turn as the starting point. The||operator skips the right call when the left one already returnedtrue. - Declare the helper.
isSameTreetakes two*TreeNodevalues,pandq, and returns abool. It sits belowisSubtree, and Go allows calling a function that is declared later in the file. - Both empty means the same. If
p == nil && q == nil, returntrue. Two empty trees are equal, and this is how the recursion ends when both sides run out of nodes together. - Exactly one empty means different. The first check already handled "both empty", so if
p == nil || q == nilnow holds, one tree has a node where the other has none. The shapes differ, so returnfalse. - Compare the values. Both nodes exist at this point, so reading
p.Valandq.Valis safe. If they differ, returnfalse. - Compare the children. The roots match, so the trees are equal exactly when the left subtrees are equal and the right subtrees are equal:
isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right).
The solution in Go
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
if root == nil {
return false
}
if isSameTree(root, subRoot) {
return true
}
return isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
if p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
The Go details worth knowing:
- Pointers and
nil. A child that is missing is anilpointer, sop == nilis the way to ask "is there a node here?". Readingp.Valon anilpointer would panic, which is why thenilchecks come first and in that order. - Short-circuit operators.
||and&&evaluate their right side only when needed. InisSameTree, a mismatch on the left stops the work before the right subtrees are touched. - Comparing structure, not pointers.
p == qwould ask whether both variables point to the same node in memory. Two separately built trees with equal contents are different pointers, so the function compares values and recurses instead. - Declaration order. Package-level functions can call each other regardless of where they appear in the file, so
isSubtreemay useisSameTreebefore it is written.
Complexity
Time: O(n · m). isSubtree reaches each of the n nodes of root at most once. At each node, isSameTree visits at most as many node pairs as subRoot has nodes, since every recursive step moves down in q and the recursion ends when q runs out. The worst case is a tree where many nodes look like the beginning of subRoot, for example a long chain of 1s compared against a shorter chain of 1s with a different last value.
Space: O(h), where h is the height of root. The only extra memory is the recursion stack, whose depth is at most the height of root plus the height of subRoot. The lesson's trees are at most 400 levels deep.
Edge cases and common mistakes
- Whole tree equals the subtree.
root = [1]andsubRoot = [1]returnstrue, becauseisSameTreesucceeds at the very first node. - Same value, different shape. With
root = [1,2,3]andsubRoot = [3], the answer istrue, since the node 3 is a leaf. Withroot = [1,2]andsubRoot = [2,3]it isfalse: the node 2 has no child 3. - Matching only the top part. A comparison that stops when
subRootruns out of nodes would accept a bigger tree whose upper part looks likesubRoot. That is whyisSameTreetreats "one side isnil, the other is not" as a mismatch. The second example in the statement tests this. - Left versus right. A tree with a left child 2 is different from a tree with a right child 2. Comparing
LeftwithLeftandRightwithRightkeeps the position of every node part of the comparison. - Forgetting the empty-tree base case. Without
root == nilat the top ofisSubtree, the recursion would eventually callisSameTree(nil, subRoot)and then try to readroot.Lefton anilpointer. - Comparing the wrong things. Comparing only the values, for example by collecting both trees into slices without marking missing children, can call two different shapes equal.
Testing
Trees are written in level order, with nil for a missing child.
root = [3,4,5,1,2],subRoot = [4,1,2]givestrue.root = [3,4,5,1,2,nil,nil,nil,nil,0],subRoot = [4,1,2]givesfalse.root = [1,1],subRoot = [1]givestrue.root = [1],subRoot = [1]givestrue.root = [1,2,3],subRoot = [3]givestrue.root = [1,2],subRoot = [2,3]givesfalse.root = [1,2,3],subRoot = [4]givesfalse.root = [1,nil,1,nil,1,nil,1],subRoot = [1,nil,1]givestrue.
