Symmetric Tree, Iteratively: Mirror Pairs in a BFS Queue
Check whether a binary tree mirrors itself without recursion. The iterative BFS-queue solution to Symmetric Tree, with a worked walkthrough, code, and complexity.
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 mirror image of its right half — fold it down the middle and the two sides line up. The recursive check for this is a classic three-line function, but recursion quietly leans on the call stack, and on a deep or skewed tree that stack can overflow.
The iterative version keeps the exact same logic and swaps the hidden call stack for an explicit BFS queue you control. You enqueue the pairs of nodes that should mirror each other, pull them two at a time, and verify. Same answer, no recursion depth risk — and it makes the "mirror pair" idea impossible to miss.
The problem
Given the root of a binary tree, return true if the tree is a mirror image of itself around its center, and false otherwise.
Mirror symmetry means: for every node on the left, the corresponding position on the right holds a node with the same value — and their children are mirrored too. The outer child on the left matches the outer child on the right; the inner children match across the center.
1 1
/ \ / \
2 2 2 2
/ \ / \ / \ \
3 4 4 3 3 4 3
Input: [1,2,2,3,4,4,3] Input: [1,2,2,null,3,null,3]
Output: true Output: falseThe left tree folds perfectly: 2 mirrors 2, then 3 mirrors 3 and 4 mirrors 4. The right tree fails — the left 2 has no left child while the right 2 has no left child either, but their remaining children (3 on both sides) sit in positions that don't mirror.
The recursive baseline
The natural first solution is recursion. Symmetry of the whole tree reduces to: are root.left and root.right mirrors of each other?
function isSymmetric(root) {
if (!root) return true;
return isMirror(root.left, root.right);
}
function isMirror(a, b) {
if (!a && !b) return true; // both empty → mirrored here
if (!a || !b) return false; // one empty, one not → fail
if (a.val !== b.val) return false;
return isMirror(a.left, b.right) // outer children
&& isMirror(a.right, b.left); // inner children
}This is correct and clean. The catch is the call stack: each nested isMirror call adds a frame, and the recursion goes as deep as the tree is tall. On a balanced tree that's O(log n) frames, but on a pathological, near-linear tree of 10⁵ nodes it can be O(n) frames deep — enough to blow the stack in a language with a modest limit. The iterative version removes that dependency entirely.
The key insight: enqueue the crossed pairs
Look at the two recursive calls at the bottom of isMirror:
isMirror(a.left, b.right) ← outer pair
isMirror(a.right, b.left) ← inner pairEvery recursive call is really just "here is one more pair of positions that must mirror each other." The recursion is doing nothing but scheduling pairs to compare. If you keep those pending pairs in a queue instead of on the call stack, you can process them in a plain loop.
The crossing is the whole trick: a's left child is paired with b's right child, and a's right child with b's left child. That diagonal cross is what "mirror" means. Swap it for a straight pairing (a.left with b.left) and you'd be checking whether the tree equals itself, not whether it mirrors itself.
The optimal solution
Seed a queue with the root's two children, then repeatedly shift two entries — one mirror pair — and validate. When a pair's values match, push its two crossed child-pairs onto the back of the queue.
var isSymmetric = function(root) {
let q = [root.left, root.right];
while (q.length) {
let p1 = q.shift();
let p2 = q.shift();
if (!p1 && !p2) continue; // both null → this pair mirrors
if (!p1 || !p2) return false; // exactly one null → asymmetric
if (p1.val != p2.val) return false;
q.push(p1.left, p2.right); // outer pair
q.push(p1.right, p2.left); // inner pair
}
return true;
};Three guards, in order, handle every case for a dequeued pair:
- Both null — the two mirror positions are empty, which matches. Skip to the next pair with
continue. This is the successful base case; treating it as a failure is the most common bug. - Exactly one null — one side has a node, the other doesn't. The shapes can't mirror, so short-circuit to
false. - Values differ — both are nodes but hold different values. Not symmetric, return
false.
If a pair survives all three guards, its children still need checking, so you enqueue the outer pair (p1.left, p2.right) and the inner pair (p1.right, p2.left). When the queue drains without ever hitting a failure, every mirror position agreed and the tree is symmetric.
Walkthrough
Trace root = [1,2,2,3,4,4,3] — the symmetric tree from earlier. The queue holds one mirror pair per two entries; the table shows it grouped as pairs after each step.
| Step | p1 | p2 | Guard result | Queue after (as pairs) |
|---|---|---|---|---|
| Seed | — | — | — | (2, 2) |
| 1 | 2 | 2 | 2 == 2 → push children | (3, 3), (4, 4) |
| 2 | 3 | 3 | 3 == 3 → push children | (4, 4), (∅, ∅), (∅, ∅) |
| 3 | 4 | 4 | 4 == 4 → push children | (∅, ∅), (∅, ∅), (∅, ∅), (∅, ∅) |
| 4 | null | null | both null → continue | (∅, ∅), (∅, ∅), (∅, ∅) |
| 5 | null | null | both null → continue | (∅, ∅), (∅, ∅) |
| 6 | null | null | both null → continue | (∅, ∅) |
| 7 | null | null | both null → continue | empty |
| End | — | — | queue drained | → return true |
Step 1 is where the crossing shows up. p1 = 2 is the root's left child; p2 = 2 is the root's right child. Their values match, so we enqueue p1.left (3) with p2.right (3) as the outer pair and p1.right (4) with p2.left (4) as the inner pair. Every subsequent pair is either two equal nodes or two nulls, so no guard ever fires false, and the loop exits cleanly.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Recursive mirror | O(n) | O(h) | one comparison per node; call stack as deep as the tree height h |
| Iterative BFS queue | O(n) | O(n) | one comparison per node; queue holds up to a full level, O(n) worst case |
Both approaches visit every node once, so time is O(n) for a tree of n nodes. The difference is where the pending work lives. Recursion stores it on the call stack, bounded by tree height h (which degrades to O(n) on a skewed tree). The iterative version stores it in an explicit queue that can hold an entire tree level — O(n) in the worst case — but it will never overflow the call stack no matter how deep the tree gets.
Common mistakes
- Treating both-null as a failure. When both
p1andp2are null, that pair matches — two empty positions mirror perfectly. Returnfalsehere and every symmetric tree with missing subtrees reports asymmetric. - Pairing straight instead of crossed. Enqueuing
(p1.left, p2.left)and(p1.right, p2.right)checks whether the tree equals itself, not whether it mirrors. You must cross:(p1.left, p2.right)and(p1.right, p2.left). - Checking
p1.val != p2.valbefore the null guards. If you read.valbefore confirming both nodes are non-null, a null pair throws aTypeError. Order matters: both-null, then one-null, then value. - Forgetting the empty-root case. If
rootis null, the tree is trivially symmetric. Seedingq = [root.left, root.right]on a null root throws — guard it, or rely on the problem's guarantee that the tree has at least one node.
Where this pattern shows up next
The "flatten recursion into an explicit queue or stack" move is one of the most transferable techniques in tree problems. Once you've seen it here, the iterative traversals are the same idea applied to a single tree instead of a mirror pair:
- Binary Tree Preorder Traversal — the recursive baseline that the iterative versions replace.
- Binary Tree Inorder Traversal — recursion for the left-root-right order.
- Binary Tree Preorder Traversal - Iterative — the same call-stack-into-explicit-stack conversion for preorder.
- Binary Tree Inorder Traversal - Iterative — inorder without recursion, tracking state by hand.
You can also step through Symmetric Tree interactively to watch the queue fill with mirror pairs and drain as each one is validated.
FAQ
Why use an iterative solution when the recursion is shorter?
The recursion is shorter and just as fast, but it relies on the call stack, which grows with the tree's height. On a deeply skewed tree — thousands of nodes in a near-linear chain — that stack can overflow before the algorithm finishes. The iterative BFS keeps the pending pairs in an explicit queue on the heap, so it handles arbitrarily deep trees without risking a stack overflow. Both are O(n) time; the iterative version trades stack space for queue space you control.
What does "crossed pair" mean and why does it matter?
Mirror symmetry pairs a node's left child with the other node's right child, and its right child with the other's left child. That diagonal crossing is the definition of a mirror: the outer edge of the left subtree lines up with the outer edge of the right subtree. If you instead pair left-with-left and right-with-right, you're testing whether the tree is identical to itself — which is always true — rather than whether it mirrors. The q.push(p1.left, p2.right) and q.push(p1.right, p2.left) lines encode exactly this cross.
Why is a both-null pair a success and not a failure?
Two null positions mean both mirror slots are empty at that spot, which is perfectly symmetric — nothing on the left, nothing on the right. The failure case is exactly one null: one side has a node while its mirror position is empty, so the shapes can't match. That's why the guards run in order — both-null (continue) first, then one-null (return false) — so an empty-empty pair is skipped rather than rejected.
What is the time and space complexity?
Time is O(n) for a tree of n nodes, because each node is dequeued and compared exactly once. Space is O(n) in the worst case: the queue can hold an entire level of the tree, and the widest level of a balanced tree contains up to n/2 nodes. The recursive alternative uses O(h) stack space, where h is the height — better on balanced trees but as bad as O(n) when the tree is skewed.
Does this work for trees with duplicate values?
Yes. The check only ever compares a node against its single mirror partner, so repeated values elsewhere in the tree never interfere. A tree like [1,2,2,2,null,2] fails not because the 2s repeat but because the structure doesn't mirror — the left 2 has a left child while the right 2 has a right child, so a one-null guard eventually fires. Values and structure are validated together, pair by pair.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.