LeetCode 100 – Same Tree

Same Tree is the smallest possible tree recursion, and it earns its place by being the template the harder tree problems are written against. Three base cases and one recursive step — and the order of those base cases is the only thing that can go wrong.

The problem

Given the roots of two binary trees, return whether they are identical: the same structure and the same values at every position.

  1        1
 / \      / \       -> true
2   3    2   3

  1        1
 /          \       -> false   same values, different shape
2            2

  1        1
 / \      / \       -> false   same shape, different values
2   1    1   2

null and null       -> true
null and [1]        -> false

The second pair is the one worth pausing on. Both trees contain exactly the values {1, 2}. Structure is part of the answer, not just contents.

Three base cases, in order

1. both null            -> true      two empty trees are the same tree
2. exactly one null     -> false     structures differ
3. values differ        -> false
otherwise               -> recurse on both pairs of children

The order matters and is the whole trick. Case 1 must come first, because case 2's test is "one of them is null" and it would fire on two nulls if it were checked first. Case 3 dereferences both nodes, so it is only safe once cases 1 and 2 have ruled out every null — putting the value comparison first is a null-pointer exception waiting for the first mismatched shape.

Written as a chain, each case protects the next. Say that out loud; it is the difference between having reasoned about the ordering and having got lucky.

Java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;    // both empty
        if (p == null || q == null) return false;   // exactly one empty -- shapes differ
        if (p.val != q.val) return false;           // safe: neither is null by now

        return isSameTree(p.left, q.left)
            && isSameTree(p.right, q.right);
    }
}

&& short-circuits, so a mismatch in the left subtree means the right is never walked. On two large trees differing near the root that turns a full traversal into a couple of calls — a free optimisation that comes from writing the natural thing.

Both trees are descended in lockstep. There is no search: position i in one is only ever compared against position i in the other, which is what makes this O(n) rather than something much worse.

Python

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        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 (self.isSameTree(p.left, q.left)
                and self.isSameTree(p.right, q.right))

is None rather than == None — identity, not equality, so a TreeNode with a custom __eq__ cannot change the meaning of the check.

Resist compressing this to if not p or not q. A node whose value is 0 is not falsy — TreeNode objects are always truthy — but the habit is dangerous, and the identical-looking shortcut on integers or lists is a real bug.

The iterative version

If asked to avoid recursion, walk both trees together with one queue holding pairs:

    boolean isSameTreeIterative(TreeNode p, TreeNode q) {
        Deque<TreeNode[]> queue = new ArrayDeque<>();
        queue.add(new TreeNode[]{p, q});

        while (!queue.isEmpty()) {
            TreeNode[] pair = queue.poll();
            TreeNode a = pair[0], b = pair[1];

            if (a == null && b == null) continue;      // this branch matches
            if (a == null || b == null) return false;
            if (a.val != b.val) return false;

            queue.add(new TreeNode[]{a.left, b.left});
            queue.add(new TreeNode[]{a.right, b.right});
        }

        return true;
    }

The same three cases, with continue where the recursion had return true — a matching empty branch means "nothing more to check here", not "the whole answer is true". That substitution is the one thing that changes when a boolean recursion becomes a worklist loop, and it is the transferable part.

Complexity

n is the size of the smaller tree, since traversal stops at the first structural difference. The recursive space is the height, the iterative is the width — worth knowing that DFS and BFS trade one for the other, and which is worse depends on the tree: a degenerate tree is deep and narrow, a complete tree is shallow and wide.

The pattern

Two trees walked in lockstep recurs constantly. Symmetric Tree (101) is this with the children crossed — compare a.left against b.right — which is a one-line change and a genuinely clever one. Subtree of Another Tree (572) calls isSameTree at every node of the larger tree. Merge Two Binary Trees (617) has the identical base-case structure and builds a node instead of returning a boolean.

Getting the three base cases automatic here is what makes those three feel easy rather than fiddly.

What the interviewer is checking

• All three base cases, in an order where each protects the next.
• That structure counts, not just the multiset of values.
• Two empty trees returning true.
• That the value comparison never dereferences a null.
• That && short-circuits on the first mismatch.
• O(h) stack versus O(w) queue if asked to go iterative.
• That you can adapt it to Symmetric Tree without starting over.