Symmetric Tree
Symmetric Tree: is the tree a mirror of itself around its center?
- The number of nodes in the tree is in the range [1, 1000].
- -100 <= Node.val <= 100
Intuition
A symmetric tree is one that looks unchanged in a mirror — fold it down the middle and the two halves line up. The trap is trying to express that as a property of single nodes. Symmetry is not something a node has; it is a relationship between two nodes sitting in mirrored positions.
So instead of asking "is this tree symmetric," ask the question that actually recurses: are these two subtrees mirror images of each other? The root is symmetric exactly when its left and right children mirror one another, which turns the whole problem into one call on a pair.
Now work out what mirroring means for a pair (a, b). Their values must be equal, and then the children have to cross:
- a's left pairs with b's right, and a's right pairs with b's left.
That crossing is the entire difference between this problem and Same Tree, which pairs left with left. Everything else — the null handling, the and chain, the complexity — is identical. If you can already write Same Tree, you can write this one by swapping two arguments in the recursive call, and it is worth writing both to see how small the difference is.
The null cases work the same way as well: two nulls mirror each other fine, one null against a real node is an immediate structural mismatch.
Symmetry is same-tree with one pairing changed. Instead of comparing left-to-left, you compare each subtree against its mirror — left against right. Whenever a problem is about reflection rather than equality, look for the place where the recursive call's arguments should cross over.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Reframe the question as a pair comparison
Define a helper mirror(a, b) that answers whether two subtrees are reflections of each other. The top-level answer is then mirror(root.left, root.right). An empty tree is symmetric by convention, so handle a null root by returning true before calling the helper.
Two nulls mirror each other
If both a and b are null, this mirrored position is consistent — return true. As in Same Tree, this check must come before the single-null check, or the both-null case gets misreported as a mismatch.
One null breaks the reflection
If exactly one of the two is null, one side has a node where the other has empty space, so the tree cannot fold onto itself. Return false. This is the check that catches shape asymmetry, which value comparison alone will never find.
Compare the paired values
With both nodes present, a.val must equal b.val. These are nodes at mirrored positions, not parent and child, so this is comparing across the fold rather than down the tree.
Recurse with the children crossed
Return mirror(a.left, b.right) and mirror(a.right, b.left). The crossing is the whole algorithm — outer child against outer child, inner against inner. Pairing left with left instead silently turns this into an equality test and will accept trees that are not symmetric.
Cost of the traversal
Every node is visited once as part of exactly one pair, so the time is O(n). The recursion depth follows the tree height, giving O(h) space: O(log n) when balanced, O(n) for a degenerate chain.
The queue-based version
Push root.left and root.right onto a queue, then repeatedly dequeue two nodes and apply the same checks, enqueuing the four children in crossed order: a.left, b.right, a.right, b.left. Same complexity, no recursion stack, and the crossed enqueue order is exactly the crossed recursive call written out flat.
Solution & live demo
Common pitfalls
Recursing on matching sides instead of mirrored ones
return (a.val == b.val
and mirror(a.left, b.left)
and mirror(a.right, b.right))return (a.val == b.val
and mirror(a.left, b.right)
and mirror(a.right, b.left))That tests whether the two subtrees are identical, not mirrored — it would reject [1,2,2,3,4,4,3], which is symmetric. A reflection maps the leftmost node to the rightmost, so the calls must cross.
Comparing the root with itself
return mirror(root, root)
return not root or mirror(root.left, root.right)
It happens to work, because crossing the arguments makes the root trivially match itself — but it obscures the actual claim, which is that the root's two children are mirrors of each other. Starting from the children states the invariant you're relying on.
Edge cases
Shape matches but not mirrored (both 3s on the same side) → False — the cross-pairing catches it.
Symmetric by convention → True.