Subtree of Another Tree: Recursive Tree Matching

You are given two binary trees, root and subRoot. Return True if there is a subtree of root that has the exact same structure and node values as subRoot.

This is LeetCode 572: Subtree of Another Tree, and it is one of the best problems for practicing tree matching recursion. If you have already solved Maximum Depth of Binary Tree and Symmetric Tree, you know the recursive null base case pattern and the idea of comparing two trees in parallel. Subtree of Another Tree combines both of those skills: you walk through every node in the main tree, and at each node you ask "does the tree rooted here look exactly like subRoot?"

Why this problem matters

Most tree problems ask you to do something with a single tree. Subtree of Another Tree asks you to compare two trees, and it does so repeatedly. You need two layers of recursion:

1. An outer traversal that visits every node in the main tree as a potential match point
2. An inner comparison that checks whether the subtree rooted at the current node is identical to subRoot

That nested structure trips people up the first time they see it. But once you understand that the outer function just walks the tree and the inner function does a Same Tree check (LeetCode 100), it clicks. You are composing two simple recursive patterns into one solution.

The key insight

A subtree match means every single node lines up. Same values, same structure, same null positions. It is not enough for the values to appear somewhere in the tree. The entire shape of subRoot must be replicated exactly starting from some node in root.

So the algorithm is:

1. For every node in root, ask: "Is the tree rooted here identical to subRoot?"
2. If yes, return True. If no, try the left child and the right child.
3. The "identical" check is a classic Same Tree comparison: both null returns True, one null returns False, values must match, and both children must match recursively.

The recursive solution

def is_subtree(root, sub_root):
    if root is None:
        return False
    if is_same(root, sub_root):
        return True
    return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)

def is_same(s, t):
    if s is None and t is None:
        return True
    if s is None or t is None:
        return False
    return (s.val == t.val
            and is_same(s.left, t.left)
            and is_same(s.right, t.right))

Let's break this down:

• is_subtree is the outer traversal. If the current node is None, there is no tree left to match against, so return False.
• is_same(root, sub_root) asks: "Is the tree starting here an exact copy of sub_root?" If yes, we are done.
• If not, we recurse into root.left and root.right. If either subtree contains a match, we return True.
• is_same is the inner comparison. Two null nodes match (base case). One null and one non-null do not match. If both exist, values must be equal and both pairs of children must match recursively.

Visual walkthrough

Let's trace through the example where root = [3, 4, 5, 1, 2] and subRoot = [4, 1, 2]. We try each node in the main tree as a potential match point until we find one that works.

Notice the two layers. The outer loop tried node 3 first and the comparison failed immediately (3 != 4). Then it moved to node 4, where the comparison succeeded all the way down to the leaves. The moment is_same returns True, we short-circuit and return True from is_subtree.

What about a mismatch?

Imagine subRoot = [4, 1, 3] instead. The outer traversal would still reach node 4 and call is_same(4, 4). The roots match. Then it would compare left children (1 == 1, good) and right children (2 != 3, fail). is_same returns False. The outer traversal keeps going to nodes 1, 2, and 5, but none of them match the subtree root value of 4, so they all fail quickly. The final answer would be False.

This shows why the algorithm is correct: it exhaustively tries every node, and the is_same check is strict enough to reject partial matches.

Complexity analysis

Time is O(m * n) in the worst case, where m is the number of nodes in root and n is the number of nodes in subRoot. For each of the m nodes in the main tree, we might run an O(n) comparison against subRoot. In practice it is much faster because most comparisons fail at the first node.

Space is O(h), where h is the height of the main tree, because the recursion stack can go as deep as the tree. For a balanced tree, h = log(m).

Edge cases to watch for

Before submitting, think about these:

• subRoot is a single node: the comparison still works. You just need to find a leaf in root with the same value.
• root is None: return False. An empty tree has no subtrees to match against.
• subRoot is None: by the LeetCode definition, a null subtree is considered a subtree of any tree. However, the problem constraints guarantee subRoot has at least one node, so this edge case does not come up in practice.
• Duplicate values: the structure must match too. If root has a node with value 4 but different children than subRoot, the comparison correctly rejects it because is_same checks the entire subtree, not just the root value.
• Subtree at a leaf: the match can happen anywhere, including at the deepest leaves of the main tree.

The building blocks

This problem is built on one fundamental brick: the recursive null base case pattern for trees.

def solve(node):
    if node is None:
        return BASE_VALUE
    left = solve(node.left)
    right = solve(node.right)
    return COMBINE(left, right)

For Subtree of Another Tree, you use this skeleton twice. The outer function (is_subtree) uses it to traverse the main tree, with BASE_VALUE as False and COMBINE as is_same(node, sub_root) or left or right. The inner function (is_same) uses it to compare two trees, with the double-null base case returning True and the single-null base case returning False.

This same recursive null base case pattern drives:

• Maximum Depth (LeetCode 104): BASE_VALUE is 0, COMBINE is 1 + max(left, right)
• Symmetric Tree (LeetCode 101): compares mirror pairs instead of corresponding pairs
• Same Tree (LeetCode 100): the is_same helper is literally this problem
• Invert Binary Tree (LeetCode 226): BASE_VALUE is None, COMBINE swaps children

Once you internalize the recursive skeleton and the "try every node as a candidate" pattern, you can handle any problem that asks "does this subtree/path/pattern exist somewhere in the tree?"

From understanding to recall

You just traced through a clean two-layer recursive solution. The outer traversal and inner comparison make sense right now. But will you remember to split it into two functions next week? Will you instinctively write the is_same helper with the double-null base case without second-guessing yourself?

Understanding is step one. Recall under pressure is step two. Spaced repetition bridges that gap. You practice typing the solution from scratch at increasing intervals. First after a day, then three days, then a week. Each repetition strengthens the neural pathway until the pattern becomes automatic.

The recursive null base case is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition beats grinding random problems every time.

Related posts

• Symmetric Tree - Another "compare two trees" problem that uses the same double-null base case, but with mirror pairs instead of corresponding pairs
• Maximum Depth of Binary Tree - The best introduction to the recursive null base case pattern that Subtree of Another Tree builds on