Problem overview
isSubtree receives the roots of two binary trees, root and subRoot. It returns True when some node of root, taken together with all of its descendants, forms exactly the same tree as subRoot: 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 val, left and right, and a missing child is None.
Take 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. If the 2 had a child 0, the node 4 would no longer match, because a subtree takes every descendant of its node. The answer for [3,4,5,1,2,None,None,None,None,0] is False.
Approach: try every node, compare whole trees
The idea splits the problem in two:
- Decide whether two trees are identical. This is a simple recursion that walks both trees in step.
- Run that comparison with
subRootagainst the tree under every node ofroot. The node can berootitself, or a node somewhere in its left or right subtree, so the search recurses down both sides.
A comparison stops as soon as the trees differ, and it can never go past the size of subRoot, because once subRoot runs out of nodes the other tree must run out at the same place or the comparison fails. So each comparison costs at most m steps, where m is the number of nodes in subRoot. With one comparison per node of root, the total is O(n · m) for n nodes in root.
There are ways to be faster, such as serialising both trees and searching for one string inside the other, but the comparison approach is the one that needs no extra data structure, and the constraints (at most 2,000 and 1,000 nodes) are small enough for it.
Step by step
- Stop on an empty tree. If
rootisNone, there is no node wheresubRootcould start, andsubRootalways has at least one node, so the answer isFalse. This is also what ends the recursion once it steps past a leaf. - Test the tree that starts at
root. IfisSameTreesays it equalssubRoot, returnTrueat once. - Otherwise look lower. Call
isSubtreeonroot.leftand onroot.right, joined withor. Together with step 2, every node ofrootgets its turn as the starting place. - Write the helper
isSameTree(self, p, q). It must answer whether two trees match in shape and values. - Both empty means equal. If both
pandqareNone, returnTrue. This ends the recursion when both trees finish at the same place. - Exactly one empty means different. Since the case of two empty trees was handled already,
not p or not qmeans one tree has a node where the other has none, so returnFalse. - Compare the values. Both nodes exist now, so it is safe to read
p.valandq.val. Different values mean different trees. - Recurse on both pairs of children. The roots match, so the trees are the same exactly when the left children match and the right children match. Join the two calls with
and.
The solution in Python
class Solution:
def isSameTree(self, p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not root:
return False
if self.isSameTree(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
Python details worth a closer look:
not rootas aNonecheck. ATreeNodeobject is always truthy (it defines no__bool__or__len__), sonot rootisTrueonly forNone. That is whyif not p and not qreads as "both empty".- Short-circuiting.
andandorstop evaluating as soon as the result is known. The right pair of subtrees is skipped when the left pair already differs, and the right subtree ofrootis skipped when the left one already containssubRoot. - Methods calling methods. The helper is a method, so it is called as
self.isSameTree(...). Its position aboveisSubtreedoesn't matter to Python, because the name is looked up when the call runs. - Recursion depth. Trees here are at most 400 levels deep, which stays under Python's default recursion limit of 1,000 calls.
Complexity
Time: O(n · m). isSubtree visits each of the n nodes of root once. At each node it runs isSameTree, which looks at no more than m nodes of subRoot.
Space: O(h), where h is the height of root. The recursion stack holds one call per level, and no other data is stored. In the worst case of a one-sided tree, that is O(n).
Edge cases and common mistakes
- Checking only the root's value. The trees
[1,2]and[1]have the same root value, but the first has an extra child, so[1]is not a subtree of it. Comparing a node must include everything below it. - Stopping when the first match is partial. In
[1,1]withsubRoot = [1], the root 1 has a child and doesn't match, but its left child is a lone 1 and does. The answer isTrue, because the search continues after a failed comparison. - Forgetting the one-sided empty case. Without the check for exactly one empty tree, the next line would read
.valonNoneand raiseAttributeError. - Repeated values. Many nodes may hold the same value, as in
[5,None,5,None,5]. Each candidate node is compared in full, so repeated values only cost time, not correctness. - A tree as a subtree of itself. Equal trees return
True, from the comparison atrootitself.
Testing
Building each tree from its level-order list and calling isSubtree gives:
root = [3,4,5,1,2],subRoot = [4,1,2]givesTrue.root = [3,4,5,1,2,None,None,None,None,0],subRoot = [4,1,2]givesFalse.root = [1,1],subRoot = [1]givesTrue.root = [1],subRoot = [2]givesFalse.root = [1,2],subRoot = [1]givesFalse.root = [5,None,5,None,5],subRoot = [5,None,5]givesTrue.
