100. Same Tree

Comparing two trees for equality is the cleanest exercise in structural recursion — the idea that a tree question is usually just the same question asked at the root and at both children. It’s a foundational move in the binary tree patterns toolkit, and once the base cases feel obvious here, half the tree problems stop looking scary.

The problem

You’re handed the roots of two binary trees, p and q, and you decide whether they’re identical — same shape and the same value at every matching node. (Full statement on LeetCode.)

“Same shape” is the part people skip over. Two trees holding the values 1, 2, 3 are not automatically equal — if one leans left and the other leans right, they differ. A node with a left child is not the same as a node with a right child, even when the values line up.

Intuition: two nodes match, and so do their children

Ask the equality question at a single pair of nodes and it almost answers itself. Two nodes are “the same” when three things hold: they’re both present, they carry the same value, and — recursively — their left subtrees match and their right subtrees match.

That gives three base cases before any recursion:

• Both nodes are null → nothing to compare, so they’re equal here. Return true.
• Exactly one is null → one tree ran out of nodes before the other. The shapes differ. Return false.
• Both exist but values differ → not equal. Return false.

The order matters. Check both-null first, because if you tested p.val before ruling out null you’d hit a NullPointerException the moment either side ends. Only once both nodes are known to exist and agree do you push the same question down to (p.left, q.left) and (p.right, q.right).

Because you touch each node at most once, the work is $O(n)$ over the $n$ nodes of the smaller tree — a mismatch short-circuits the rest.

Solution

The recursion reads exactly like the three cases above:

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // both empty at this spot — equal so far
        if (p == null && q == null) return true;
        // one side ended before the other — different shape
        if (p == null || q == null) return false;
        // both present but values disagree
        if (p.val != q.val) return false;
        // values match; the trees are equal iff both subtrees are
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

The && does quiet but important work: the instant a left subtree comes back false, Java skips the right subtree entirely and unwinds. No wasted comparisons past the first mismatch.

If recursion depth worries you — a pathological, list-shaped tree can push the call stack to $n$ frames — the same logic runs iteratively with a queue. Enqueue the two roots together, then pull and check them in pairs:

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(p);
        queue.offer(q);
        while (!queue.isEmpty()) {
            TreeNode a = queue.poll();
            TreeNode b = queue.poll();       // always pull in matched pairs
            if (a == null && b == null) continue;
            if (a == null || b == null) return false;
            if (a.val != b.val) return false;
            queue.offer(a.left);
            queue.offer(b.left);
            queue.offer(a.right);
            queue.offer(b.right);
        }
        return true;
    }
}

Enqueuing null children on purpose is what keeps the two trees in lockstep — a missing node on one side and a real node on the other surface as an a == null || b == null mismatch on the next pop.

Complexity

Approach	Time	Space
Recursive DFS	$O(n)$	$O(h)$
Iterative BFS	$O(n)$	$O(n)$

Here $n$ is the node count and $h$ the tree height. The recursion spends $O(h)$ on the call stack — $O(\log n)$ when balanced, $O(n)$ in the worst case. The queue version holds a level’s worth of nodes, up to $O(n)$ for a wide tree.

In an interview

Say the recurrence in one breath before writing anything: “two trees are equal when the roots match and both pairs of subtrees are equal.” That framing tells the interviewer you see the self-similar structure, which is the actual skill being tested.

The trap is ordering the null checks wrong. Reach for p.val before you’ve confirmed p isn’t null and you’ve got a crash on the very first empty child — flag that you check both-null, then one-null, then values, on purpose. If they ask to avoid recursion (deep-tree stack concerns), reach for the queue.

This exact isSameTree helper is the engine behind Subtree of Another Tree, which just calls it at every node of the bigger tree. The same “recurse on both children” backbone drives Validate Binary Search Tree; the binary tree patterns hub connects the family.

References

• LeetCode 100 — Same Tree