Subtree of Another Tree

Subtree of Another Tree asks whether one whole tree shows up, untouched, inside another. It is the perfect place to learn how to combine two recursions: one that walks a tree, and one that compares two trees.

The slow way first

The naive instinct is to flatten both trees into strings and check if one string contains the other. That can work, but it is fiddly (you have to handle null markers carefully to avoid false matches) and easy to get subtly wrong.

A cleaner question to ask: for each node in the big tree, is the subtree hanging off it identical to subRoot? If any node answers yes, we are done. That turns the problem into two simple, well-understood pieces.

The idea: walk one tree, compare at every node

Split the work in two. A helper same_tree(a, b) returns whether two trees are exactly equal — same shape, same values — by comparing roots and recursing into both pairs of children. Then is_subtree(root, subRoot) walks every node of the big tree and calls same_tree(node, subRoot); the first node where it returns true is our answer.

The key insight: equality is its own recursion. same_tree is the classic "are these two trees identical" check, and is_subtree simply tries it at every candidate node.

Walk through it

Step through the animation. We test node 3 first: roots differ (3 vs 4), so no match. We move to node 4 and run the equality check — its value matches, its left child 1 matches subRoot's 1, and its right child 2 matches subRoot's 2. Every node lines up, so same_tree returns true and the subtree rooted at node 4 is our match.

Pseudocode

function is_subtree(root, subRoot):
    if root is empty:
        return False                      # ran off the tree, no match
    if same_tree(root, subRoot):
        return True                       # found an identical subtree here
    return is_subtree(root.left, subRoot) # else try the children
        or is_subtree(root.right, subRoot)
 
function same_tree(a, b):
    if both a and b are empty: return True
    if exactly one is empty, or values differ: return False
    return same_tree(a.left, b.left) and same_tree(a.right, b.right)

The Python solution

def is_subtree(root, sub_root):
    if root is None:
        return False
    if same_tree(root, sub_root):
        return True
    return is_subtree(root.left, sub_root) or \
           is_subtree(root.right, sub_root)
 
def same_tree(a, b):
    if a is None and b is None:
        return True
    if a is None or b is None or a.val != b.val:
        return False
    return (same_tree(a.left, b.left)
            and same_tree(a.right, b.right))

• is_subtree is the walker: if the current node is None we bottom out with False.
• At each node we call same_tree(root, sub_root) — the equality check. If it returns True, this subtree matches, so return True.
• Otherwise we recurse into the left and right children with or, so the first match anywhere short-circuits the whole search.
• same_tree returns True only when both nodes are None at the same time (structure matches at this branch).
• If exactly one is None, or the values differ, the trees diverge here, so it returns False.
• The final line demands both subtrees match, recursing left-to-left and right-to-right.

Complexity

We let m be the number of nodes in the big tree and n the number in subRoot. The space is the recursion depth, bounded by the heights of the two trees.

When this pattern shows up

Practice