Same Tree

Same Tree is a clean introduction to recursing over two trees at once. It teaches the core move for almost every binary-tree problem: handle the None base cases first, check the current node, then recurse into the children.

The slow way first

You might think to serialize each tree into a string and compare the strings, or collect all values into lists. That can work, but it is fiddly: you have to encode the null gaps carefully, or two different shapes serialize to the same list and you get a wrong answer. It is also extra memory for no benefit.

The question to ask: what does "same" actually mean at a single node? If I can decide whether one pair of nodes matches, recursion handles the rest of the tree for free.

The idea: compare one pair, then recurse

Walk both trees in lockstep. At each step we look at a pair of nodes, p and q, and ask three questions in order:

1. Are both None? Then this branch is fine — return True.
2. Is exactly one None (or do the values differ)? Then the trees differ here — return False.
3. Otherwise both are present with equal values — recurse into the left pair and the right pair, and both must be True.

The order matters: the None checks come before we ever touch .val, so we never read a value off a missing node.

Walk through it

Step through the animation. Tree p is on the left, tree q on the right. We light up a matching pair at a time: roots 1 and 1, then the left children 2 and 2, then the right children 3 and 3. Every pair is present and equal, and the recursions below the leaves hit None on both sides, so every call returns True — the trees are the same.

Pseudocode

function same(p, q):
    if p and q are both None:    return True   # nothing left, matches
    if exactly one is None:      return False  # shapes differ
    if p.value != q.value:       return False  # values differ
    return same(p.left, q.left) AND same(p.right, q.right)

The Python solution

def is_same_tree(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.val != q.val:
        return False
    return (is_same_tree(p.left, q.left)
            and is_same_tree(p.right, q.right))

• Lines 2-3 are the base case: two None nodes line up, so that branch matches — return True.
• Lines 4-5 catch a structure mismatch: one side ran out of nodes while the other did not.
• Lines 6-7 catch a value mismatch: both nodes exist but hold different numbers.
• Lines 8-9 are the recursive case: compare the left pair and the right pair, and require both with and. If either subtree differs, the whole call returns False.

Complexity

We visit each node at most once, so time is O(n) where n is the number of nodes. The extra space is O(h) for the recursion stack, where h is the tree height — O(log n) for a balanced tree, O(n) for a skewed one.

When this pattern shows up

Practice