Symmetric Tree: The Mirror Recursion Pattern
Check if a binary tree is a mirror of itself with the recursive mirror pattern — intuition, JavaScript code, a worked walkthrough, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A binary tree is symmetric when its left half is a perfect mirror of its right half — fold it down the middle and the two sides line up. The problem sounds like it's about one tree, but the trick is to stop thinking about one tree at all.
The insight that unlocks it: symmetry isn't a property of a single node, it's a relationship between two nodes. Once you compare the left subtree against the right subtree as a pair — with one small twist in how you descend — the whole thing collapses into four lines of recursion.
That reframe (compare two things, recurse with swapped sides) is the same move behind Same Tree, subtree matching, and half the "does this structure match that structure?" questions you'll see.
The problem
Given the root of a binary tree, return true if the tree is symmetric around its center — a mirror image of itself.
Input: 1
/ \
2 2
/ \ / \
3 4 4 3
Output: true // left subtree is the mirror of the right subtreeCompare that to a tree that is not symmetric:
Input: 1
/ \
2 2
\ \
3 3 (both 3s hang on the right)
Output: false // node 2's right child mirrors node 2's right child — not its leftThe second tree has the same values on both sides, so a naive "do both halves contain the same numbers?" check would wrongly pass it. Symmetry is about position, not just contents: the leftmost node on the left must line up with the rightmost node on the right.
The brute force baseline
The most literal way to check "is this tree its own mirror?" is to actually build the mirror and compare the two trees node by node.
function isSymmetric(root) {
return isSameTree(root, mirror(root));
}
function mirror(node) {
if (!node) return null;
// clone the node with its children swapped
return { val: node.val, left: mirror(node.right), right: mirror(node.left) };
}
function isSameTree(a, b) {
if (!a && !b) return true;
if (!a || !b) return false;
return a.val === b.val
&& isSameTree(a.left, b.left)
&& isSameTree(a.right, b.right);
}This is correct, but wasteful. mirror allocates a complete duplicate tree — n brand-new nodes — just to throw it away after the comparison. You walk the tree once to build the copy, then walk both trees again to compare them. That's two full traversals plus O(n) of scratch memory that exists for no reason other than to be compared and discarded.
The fix is to fuse the two steps: mirror and compare at the same time, in a single pass, without ever building the copy.
The key insight
Stop asking "is this tree symmetric?" and start asking "are these two nodes mirror images of each other?"
Two nodes left and right mirror each other when three things hold:
- both are null (empty positions match), or
- both exist, their values are equal, and their children mirror in a crossed pattern.
That crossed pattern is the whole trick. For left and right to mirror:
left.leftmust mirrorright.right— the outer pair, the two nodes furthest from the center.left.rightmust mirrorright.left— the inner pair, the two nodes closest to the center.
Notice the swap: when you go left on one side, you go right on the other. That single inversion is what turns an ordinary tree comparison into a mirror comparison. A whole tree is symmetric exactly when its root's left child mirrors its root's right child.
The optimal solution
This is the exact algorithm the Symmetric Tree visualizer steps through:
function isSymmetric(root) {
if (root === null) return true;
return isMirror(root.left, root.right);
}
function isMirror(left, right) {
if (!left && !right) return true; // both empty → matched base case
if (!left || !right) return false; // exactly one empty → structure differs
if (left.val !== right.val) return false; // values differ → not a mirror
return isMirror(left.left, right.right) // outer pair
&& isMirror(left.right, right.left); // inner pair
}Read the base cases top to bottom — order matters. First, both-null is the success case that lets a branch bottom out. Next, one-null-one-present means the two sides have different shapes, so it can't be a mirror. Only after those two structural checks do you compare values, and only if values match do you recurse into the outer and inner pairs.
The && short-circuits: the moment isMirror(left.left, right.right) returns false, JavaScript never evaluates the inner pair, and false propagates straight back up the call stack. One mismatch anywhere kills the whole answer.
Walkthrough
Trace [1, 2, 2, 3, 4, 4, 3] — the symmetric tree from the problem statement. Each row is one isMirror call, in the order recursion actually fires. The stack column shows the pending (left, right) calls after that step.
| Step | isMirror call | Check | Recursion stack | Result |
|---|---|---|---|---|
| 1 | (2, 2) | both exist, 2 == 2 → recurse | (2,2) | pending |
| 2 | (3, 3) — outer of step 1 | both exist, 3 == 3 → recurse | (2,2) (3,3) | pending |
| 3 | (null, null) — outer of step 2 | both null | (2,2) (3,3) | true |
| 4 | (null, null) — inner of step 2 | both null | (2,2) (3,3) | true |
| 5 | (3, 3) returns | outer && inner both true | (2,2) | true |
| 6 | (4, 4) — inner of step 1 | both exist, 4 == 4 → recurse | (2,2) (4,4) | pending |
| 7 | (null, null) ×2 — children of step 6 | both null both times | (2,2) (4,4) | true |
| 8 | (4, 4) returns | outer && inner both true | (2,2) | true |
| 9 | (2, 2) returns | outer (step 2) && inner (step 6) true | empty | true |
Step 2 is where the crossed recursion earns its keep. Node 2's left child is the subtree [3, 4] and its right child is [4, 3]. The outer call pairs left.left = 3 with right.right = 3, and the inner call pairs left.right = 4 with right.left = 4. The values line up precisely because we swapped sides. If both children had been [3, 4] — same values, no swap — the outer pair would compare 3 against 4, mismatch, and the tree would (correctly) report false.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Mirror-and-compare | O(n) | O(n) | builds a full duplicate tree of n nodes |
| In-place mirror recursion | O(n) | O(h) | visits each node once; stack depth = tree height |
Every node participates in exactly one mirror pair, so the recursion does O(n) work total. The space is the recursion stack, which is only as deep as the tree's height h — O(log n) for a balanced tree, O(n) in the worst case of a degenerate, list-like tree. The brute-force version matches the time but pays an extra O(n) to materialize a copy it immediately discards.
Common mistakes
- Recursing without the swap. Writing
isMirror(left.left, right.left)instead ofleft.leftvsright.rightcompares the two sides identically rather than as mirrors. That checks whether the left and right subtrees are equal, not reflected — a subtly different (and wrong) answer. - Checking values before structure. If you compare
left.valbefore handling the null cases, you'll dereferencenull.valand crash the moment one side runs out of nodes before the other. - The inorder-palindrome shortcut. Flattening the tree with an inorder traversal and checking if the result reads the same forwards and backwards seems clever but fails on trees where equal values mask an asymmetric shape — the traversal loses the null placeholders that make structure visible.
- Comparing multisets of values. "Both halves have the same numbers" ignores position entirely. The second example in the problem section passes that test but is not symmetric.
Where this pattern shows up next
The "compare two nodes as a pair, recurse structurally" move generalizes directly:
- Symmetric Tree - Iterative — the same mirror check without recursion, pushing mirror pairs onto an explicit queue or stack.
- Same Tree — the un-swapped sibling: recurse into matching sides instead of crossed sides to test structural equality.
- Subtree of Another Tree — anchors a Same Tree check at every node to find one tree hiding inside another.
- Subtree of Another Tree (Serialization) — the same question reframed as substring search on a serialized tree.
You can also step through the Symmetric Tree visualizer to watch each mirror pair light up and the recursion stack grow and unwind.
FAQ
Why does Symmetric Tree compare left.left with right.right instead of left.left with right.left?
Because symmetry is a reflection, not a copy. When you descend left on one subtree, its mirror image descends right on the other. Pairing left.left with right.right (the outer nodes) and left.right with right.left (the inner nodes) is exactly the crossing that a mirror produces. Comparing the same sides would test for structural equality of the two subtrees, which is a different question with a different answer.
What is the time and space complexity of the recursive solution?
Time is O(n), where n is the number of nodes, because each node is visited exactly once as part of one mirror-pair comparison. Space is O(h), where h is the height of the tree — that's the maximum depth of the recursion stack. For a balanced tree that's O(log n); for a skewed, list-like tree it degrades to O(n).
Can Symmetric Tree be solved without recursion?
Yes. Instead of the call stack, use an explicit queue or stack that holds pairs of nodes to compare. Push the two roots as a pair, then repeatedly pop a pair, run the same null and value checks, and push their children in mirror order — left.left with right.right, then left.right with right.left. It's the identical logic with your own stack replacing the recursion. See the iterative variant for the full code.
How do I check for symmetry if the tree is empty or has one node?
Both are trivially symmetric. An empty tree (root === null) returns true immediately — there are no nodes to violate the mirror. A single node has no children, so its (empty) left and right sides mirror each other perfectly; isMirror(null, null) hits the both-null base case and returns true. These edge cases fall out of the base cases for free with no special handling.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.