A catalog service keeps the same product-category tree on a primary and a replica. Before flipping read traffic, ops wants a cheap “are they the same tree?” check. The intern version serialized both trees to preorder strings with null markers and compared the strings. Two empty catalogs matched. A missing left child versus a missing right child produced different strings, so the check was correct. A million-node catalog still built two full encodings the walk never needed to keep.

Two trees are the same only if a simultaneous walk sees the same structure and the same values. The binary tree post owns shape and traversals. Here we only care about pairing a node with its counterpart: both null, one null, values differ, then left with left and right with right.

The problem

Given the roots of two binary trees, return whether they are the same tree — identical structure, and equal values at corresponding nodes. Two empty trees are the same. Two single-node trees match when the values match. One empty and one not is not.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample trees:

      1                 1
     / \               / \
    2   3             2   3     →  true

      1                 1
     /                   \
    2                     2     →  false

[]                  []          →  true
[1]                 [1]         →  true
[]                  [1]         →  false

Note: Matching values in some order is not enough. The second drawing has the same keys and a different shape: left child versus right child. Do not drop the null markers — 1,2 from the left-child tree and 1,2 from the right-child tree look the same until you encode the holes.

Serialize both, then compare is the honest brute force

Walk each tree into a string (or list) that records values and nulls, then compare the two dumps. Correct. Extra memory: two full encodings you discard after equals.

boolean isSameTreeSerialize(TreeNode p, TreeNode q) {
    return serialize(p).equals(serialize(q));
}

String serialize(TreeNode node) {
    if (node == null) {
        return "#";
    }
    return node.val + "," + serialize(node.left) + "," + serialize(node.right);
}

At a dozen nodes this is a rounding error. At a million-node pair you still visit everyone, plus two strings proportional to the trees. The intended answer never builds those strings: fail as soon as a pair of nodes disagrees.

Pair the nodes, fail on the first mismatch

Both null: same. Exactly one null: not the same. Both present but values differ: not the same. Otherwise the lefts must match and the rights must match.

same(1, 1)  values match
  same(2, null)  one null  →  false

The Java is that walk. Short-circuit on && so a left mismatch never walks the rights.

boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }
    if (p.val != q.val) {
        return false;
    }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Time is O(n) — each paired node is checked once. Space is O(h) for the call stack, h being height. A spine of a million nodes is a million frames; the iterative version with an explicit stack of pairs is the same bound without blowing the JVM stack.

Two empty trees: both roots null, return true. One empty: the || branch returns false. Two single nodes with equal values: both present, values match, four null children, return true. Different values fail the != check. No extra branch.

What interviewers usually poke next

  • Subtree of Another Tree. Ask whether one tree appears inside another. Related idea, different contract: you may start this same-tree check at many nodes. Later sibling — do not start scanning a parent tree inside isSameTree. Optional URL: /interview/trees/easy/subtree-of-another-tree/.
  • Symmetric tree. Ask whether a tree is a mirror of itself. Compare left with right, not left with left. Later sibling. Optional URL: /interview/trees/easy/symmetric-tree/.
  • Iterative pair walk. An ArrayDeque of (p, q) pairs, same four-way check, no recursion. Mention it; write it if they ask.
  • Same values, different shape. Draw the left-child versus right-child trees. Serialization without null markers loses that case.

You are done with this problem when you can reject 1 / 2 versus 1 \ 2 without building two strings, and you can name the two-empty, one-empty, and single-node returns without a special case.