STEP 13 · BINARY TREES · RECURSE ON PAIRS, NOT NODES · EASY

Symmetric Binary Tree

WHAT IT SAYS

Decide whether a binary tree is a mirror image of itself around its center.

WHAT IT'S REALLY ASKING

"Symmetry is not a property of one node — it is a relationship between TWO subtrees that face each other across the axis. So the recursion cannot walk one tree; it must walk a pair, and at every step the pairing crosses: my left against your right, my right against your left."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Build the mirrored tree and compare

O(n) time, O(n) space for the mirror copy

Construct a full mirror copy of the tree — swap children at every node — then run the standard Same Tree lockstep check between the original and the copy.

WHERE THE WORK IS WASTED — The copy is a physical answer to a question that only needed a conceptual one. Mirroring never has to HAPPEN — it can be simulated by how you pair the nodes during comparison: whenever you would have looked at the copy's left child, look at the original's right child instead. Every node the builder allocates duplicates information the original already holds, and it materialises the entire mirror before comparing byte one, when the first mismatch might sit at depth two. You are paying O(n) memory for a change of index.

KEY OBSERVATION — THE UNLOCKlink

The unit is a facing pair, and the pairing crosses.

First, see why the obvious recursion cannot work. 'A tree is symmetric if its left subtree is symmetric and its right subtree is symmetric' is FALSE — each subtree can be individually asymmetric while the whole is a perfect mirror, and vice versa. Symmetry of the whole simply does not decompose into symmetry of the parts. That failure is the real lesson: the property is not about one subtree, so no recursion on single nodes can express it. So change the unit of recursion. Define mirror(a, b): subtrees a and b are mirror images of each other. THIS decomposes perfectly, and the decomposition has a twist that is the entire problem: a and b are mirrors exactly when their root values match, AND a's LEFT is a mirror of b's RIGHT, AND a's RIGHT is a mirror of b's LEFT. The recursion crosses at every level — outer children pair with outer, inner with inner — because that is literally what a reflection does to left and right. Why is the crossing correct and not just plausible? Track any node's position as the sequence of turns from the root. Its mirror partner is the node whose turn sequence is flipped (every L becomes R). The crossed recursion visits exactly those flipped-sequence pairs in lockstep: each recursive step appends one turn to a's path and the OPPOSITE turn to b's path. The pairing the recursion generates is precisely the pairing the reflection defines. The original question is then one call: the tree is symmetric iff mirror(root.left, root.right) — the two halves face each other across the axis. Base cases are Same Tree's, unchanged: both null is true, one null is false. Compare with Same Tree and the delta is two swapped arguments in one recursive call. One transposition is the whole difference between 'identical' and 'mirrored', which tells you both problems are the same lockstep walk with different pairings.

Crossed lockstep on (left, right)

O(n) time — every node enters exactly one pair — O(h) stack space

Write mirror(a, b): both null returns true; one null returns false; otherwise values equal AND mirror(a.left, b.right) AND mirror(a.right, b.left). Answer mirror(root.left, root.right), with an empty tree counting as symmetric. Iteratively: a queue of pairs, pushing the two crossed pairs each round — same walk, explicit stack.

WHAT YOU TRADED — Nothing is bought with memory here; the cost was conceptual — accepting that the recursion's argument is a PAIR, not a node, because the property is a relation, not an attribute. That is the transferable move: when a property relates two parts of a structure (mirrored, isomorphic, flip-equivalent), recurse on pairs of positions and encode the relationship in how each step pairs the children — crossed for mirrors, straight for equality, both-ways for flip equivalence.

WATCH THE IDEA RUN

the recursion's unit a facing PAIR, not a node

verdict holding

Symmetry is not a property of one node — it is a property of a PAIR of nodes facing each other across the mirror. So the recursion's argument must be a pair, not a node.

step 1 / 11

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Crossed Lockstep

YOU'LL SEE IT AGAIN WHEN

The property is a relation between two subtrees rather than an attribute of one — so single-node recursion cannot even state it.
The natural per-node decomposition is provably wrong (parts can fail while the whole holds), forcing the recursion's unit up to pairs.
The relationship dictates the child pairing: equality pairs straight, mirroring pairs crossed, flip-equivalence tries both.

SAME BLUEPRINT, DIFFERENT PROBLEM

Same TreeInvert Binary TreeFlip Equivalent Binary TreesSubtree of Another Tree

The bar isn't "solved it once." It's "could rebuild it from the observation."