100 · Same Tree

Two cursors descending in lockstep. The whole of sub-variant B is the three-line base case below — both null, one null, values differ — in that order, followed by a conjunction over the paired children.

1 — The problem

Two trees are the same when they have identical structure and identical values. The recursion takes two node arguments instead of one and moves them together, which is the only structural difference from sub-variant A. Everything else follows from writing the base cases in the right order:

Order	Test	What it is really deciding
1	`a == null && b == null` → true	Two absences match. This must come first, or the next line would reject it.
2	`a == null \|\| b == null` → false	Exactly one absence — a structural mismatch. Reached only when the first test failed, so "or" here means "exactly one".
3	`a.val != b.val` → false	Both exist; now, and only now, is it safe to dereference either one.
4	recurse `(a.left, b.left)` && `(a.right, b.right)`	Both pairings must hold. `&&` short-circuits, so a mismatch on the left never explores the right.

The order is not stylistic. Swap 1 and 2 and every matched pair of empty subtrees reports a mismatch; move 3 above 2 and the first structural mismatch throws a NullPointerException.

2 — Two cursors, one descent

These two trees agree on the root and on the left child, then diverge: p hangs its 4 on the left of 2, q hangs it on the right. Watch which base case catches it, and watch what happens to node 3 afterwards.

Node 3 in both trees is never compared. The && on line 5 sees false come back from the left pairing and never evaluates line 6. That is worth noticing because it is the same short-circuit that makes LC 110's sentinel cheap, and the same one that makes LC 572 tolerable.

2.1 The pairing rule is a parameter

Nothing in this machine cares that left is paired with left. Change which child is matched with which and the same six lines answer a different question:

Problem	Pairing on line 5–6	Question answered
100. Same Tree	`(a.left, b.left)` and `(a.right, b.right)`	Are these two trees identical?
101. Symmetric Tree	`(a.left, b.right)` and `(a.right, b.left)`	Is one tree a mirror of the other?
951. Flip Equivalent	either pairing, joined by `\|\|`	Can flips at some nodes make them identical?
617. Merge Two Trees	same as 100, but returning a node	What is the overlay of the two trees?

If you have written 100 and understood that the pairing is data rather than law, 101 and 951 are not new problems.

3 — Complexity and edge cases

Time O(min(m, n)) — the descent stops at the first mismatch, and it can never go deeper than the shallower tree. Space O(min(m, n)) for the stack in the worst case.
Both empty: true, by the first base case. This is the call that makes leaves work without a leaf test.
One empty: false, by the second. Note that these two lines have to be separate ifs — there is no single boolean expression that distinguishes "neither" from "exactly one" without writing both.
Same values, different shape: the case in the visualizer, and the one that casual testing misses. Trees built from [1,2,3,4] and [1,2,3,null,4] contain the same multiset of values.
Common bug: writing a.val != b.val before the null guards. It passes every test where the trees have the same shape, and throws on the first that does not.

4 — Reference implementation

Java 21Lockstep recursion, matching the visualizer.6 lines

public boolean isSameTree(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;   // both absent
    if (a == null || b == null) return false;  // exactly one absent
    if (a.val != b.val)            return false;  // safe to dereference now
    return isSameTree(a.left,  b.left)
        && isSameTree(a.right, b.right);
}

An equivalent one-liner exists — a == null || b == null ? a == b : a.val == b.val && … — and is worth being able to read, but the three explicit guards are what you want in an interview, because each one names a case you can be asked about.