Same Tree: Recursive Structure Comparison

You are given the roots of two binary trees p and q. Return True if they are structurally identical and every corresponding node has the same value. Return False otherwise.

This is LeetCode 100: Same Tree, and it is one of the purest examples of parallel tree recursion. You walk through both trees at the same time, comparing the node at each position. If every pair matches and every structural branch lines up, the trees are the same.

Why this problem matters

Same Tree is the foundation for every "compare two trees" problem. The pattern here, recursing into two nodes simultaneously and checking three conditions (both null, one null, values differ), reappears directly in Symmetric Tree and Subtree of Another Tree. In Symmetric Tree, you compare mirror pairs instead of corresponding pairs. In Subtree, you run is_same at every node as a subroutine.

If you can write the Same Tree solution from memory, those harder problems become a matter of plugging this function into a different outer loop.

The approach

The recursion follows a simple decision chain:

1. Both nodes are null. You have reached the end of both branches at the same time. They match. Return True.
2. One node is null and the other is not. One tree has a branch where the other tree has nothing. They cannot be the same. Return False.
3. Both nodes exist but their values differ. Return False.
4. Both nodes exist and their values are equal. Recurse on the left children and the right children. Only if both recursive calls return True are the subtrees the same.

That is the entire algorithm. No data structures, no preprocessing. Just a recursive function that compares two nodes and branches into two more comparisons.

The solution

def is_same_tree(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 is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

Visual walkthrough

Let's trace through p = [1, 2, 3] and q = [1, 2, 3] step by step. At each step, you compare one pair of corresponding nodes and then recurse into their children.

Notice the pattern: each call receives two nodes, checks the three conditions, and if everything passes, spawns two more calls (one for the left pair, one for the right pair). When both calls return True, the current pair is valid, and the result bubbles back up.

Complexity analysis

Time is O(n), where n is the number of nodes in the smaller tree. Every node is visited at most once as part of a pair comparison. If you hit a mismatch early, you short-circuit and skip the rest.

Space is O(h), where h is the height of the tree, because the call stack grows as deep as the recursion goes. For a balanced tree, h = log(n). For a completely skewed tree (every node has only one child), h = n.

Building blocks

This problem is built on two fundamental bricks:

1. Parallel tree recursion. Instead of recursing into a single tree, you recurse into two trees at the same time. Each call takes a pair of nodes (p, q) and compares them before branching into (p.left, q.left) and (p.right, q.right). This parallel traversal pattern is the backbone of Symmetric Tree, Merge Two Binary Trees, and any problem that asks you to compare or combine two trees.

2. Base case comparison (the double-null check). The three-way base case, both null returns True, one null returns False, values differ returns False, is a reusable template. You will write this exact sequence of checks in nearly every "compare two tree nodes" function.

if not a and not b:
    return True
if not a or not b:
    return False
if a.val != b.val:
    return False

Once this pattern is in your muscle memory, you never have to think about the base cases again. You just write them and focus on the recursion logic that differs between problems.

Edge cases to watch for

Before submitting, consider these:

• Both trees are empty (p and q are both None). Return True. Two empty trees are trivially the same.
• One tree is empty and the other is not. Return False. The "one null" check catches this on the very first call.
• Single nodes with the same value. Return True. The roots match, and both left and right children are null, which triggers the "both null" base case.
• Same structure but different values. The value comparison catches this. For example, p = [1, 2, 3] and q = [1, 2, 4] will match at the root and left child, but fail at the right child (3 != 4).
• Same values but different structure. p = [1, 2] (left child only) and q = [1, null, 2] (right child only). The "one null" check fires when comparing p.left = 2 with q.left = null.

From understanding to recall

You just traced through the cleanest possible tree comparison. The three base cases make sense. The parallel recursion makes sense. But will you reproduce this flawlessly in an interview next week? Will you remember to check "both null" before "one null"? Will you instinctively write is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right) without pausing?

Understanding is the first step. Recall under pressure is the second. Spaced repetition bridges the gap. You type the solution from scratch at increasing intervals: after one day, then three days, then a week. Each repetition reinforces the base case order, the value check, and the parallel recursion until they become automatic.

The double-null check 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 - Uses the same double-null base case pattern, but compares mirror pairs instead of corresponding pairs
• Subtree of Another Tree - Calls is_same_tree as a subroutine at every node in the main tree