Subtree of Another Tree — Solution

Problem

Given two binary trees, determine whether the second tree is an exact subtree of the first. A subtree means some node in the first tree, together with all of its descendants, is structurally identical to the second tree — values and shape must both match.

Example:

[3,4,5,1,2]

[4,1,2]

• Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
• Output: true
• Explanation: The node with value 4 in root, along with its children 1 and 2, is identical to subRoot.

Counter-example: if root's 4-node had an extra child below 2 (a node 0), subRoot [4, 1, 2] would NOT match — a subtree must account for all descendants, not just the top levels.

Intuition

At each node in the main tree, ask: "does the tree rooted here look exactly like subRoot?" We need two recursive functions — one to try every node as a candidate starting point, and one to check whether two trees are structurally identical. The moment either child subtree of root produces a match, we're done.

Solution — Recursive DFS

For each node in root, use a same-tree helper to check if the subtree rooted there equals subRoot exactly. If no match, recurse into the left and right children.

1. If root is null, return false — an empty tree cannot contain subRoot.
2. Call isSameTree(root, subRoot); if true, return true immediately.
3. Recursively check isSubtree(root.left, subRoot) and isSubtree(root.right, subRoot).
4. In isSameTree: both null → true; one null → false; values must match and both child pairs must match recursively.

1def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
2    if not root:
3        return False
4    if self._is_same_tree(root, subRoot):
5        return True  # entire subtree at this node matches subRoot
6    return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
7
8def _is_same_tree(self, node_a: Optional[TreeNode], node_b: Optional[TreeNode]) -> bool:
9    if not node_a and not node_b:
10        return True   # both exhausted simultaneously — structures match
11    if not node_a or not node_b:
12        return False  # one ended early — shapes differ
13    return (node_a.val == node_b.val
14            and self._is_same_tree(node_a.left, node_b.left)
15            and self._is_same_tree(node_a.right, node_b.right))

Time: O(n × m) where n = nodes in root and m = nodes in subRoot — in the worst case every node in root triggers a full same-tree check against subRoot.
Space: O(h) where h = height of root — the recursion stack depth is bounded by the tree's height; O(log n) for balanced trees, O(n) for a skewed tree.

Complexity Summary

Common Mistakes

• Checking only root values, not the full structure — finding a node in root whose value equals subRoot's root is not enough; isSameTree must compare the complete shape and values below that node.
• Treating a partial match as valid — if root's candidate node has extra descendants beyond what subRoot contains, it is not a subtree; isSameTree catches this because root's extra children will fail against subRoot's null nodes.
• Not short-circuiting the OR — once isSubtree(root.left, subRoot) returns true, there's no need to recurse right; the natural or / || operators handle this, but an explicit two-step check that always calls both branches wastes work.
• Confusing the two functions' roles — isSubtree traverses root to try each candidate node; isSameTree verifies exact structural equality. Attempting to combine them into one function almost always produces incorrect results for trees where values repeat.

Related Problems

• same-tree — the isSameTree helper used here is a standalone problem with the identical recursive structure
• symmetric-tree — compares left and right subtrees of the same tree using the same two-pointer recursive same-tree pattern
• path-sum — at each node, recursively checks a property rooted there; shares the outer-traversal-plus-inner-check structure
• lowest-common-ancestor-of-a-binary-tree — recursive DFS over a binary tree that collects information bottom-up at each node
• invert-binary-tree — simple recursive tree manipulation that shares the same post-order structural recursion