Loading…

easyTreesLC #101Frequently asked

Symmetric Tree

Trees & BST · 22 of 41 · 9 min

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

A tree is symmetric if the left subtree is a mirror reflection of the right subtree: the structures match and the values match when one side is read left-to-right and the other right-to-left.

In plain English

We are not traversing a single tree and checking some property of each node. We are comparing two subtrees — the left and the right — to confirm one is the reflection of the other. Reflection means the outermost nodes pair up, the next-outermost pair up, and so on, with matching values at every paired position.

Examples

Example 1

Input: root = [1,2,2,3,4,4,3]
Output: true
Note: Left subtree is (2 → 3,4), right subtree is (2 → 4,3). Reading the right side in reverse gives 3,4 — a perfect mirror of the left.

Example 2

Input: root = [1,2,2,null,3,null,3]
Output: false
Note: Both 2s have a single child, but the left's child is on the right and the right's child is also on the right. They don't mirror — the 3s should land on opposite sides.

Example 3

Input: root = [1]
Output: true
Note: A single node has two empty subtrees, which trivially mirror each other.

Constraints

The number of nodes is in the range [1, 1000]
-100 ≤ Node.val ≤ 100
Follow-up: solve it both recursively and iteratively

Clarifying questions4First question: Does symmetry require matching values, or only matching structure?Explore questions

Q1.Does symmetry require matching values, or only matching structure?
Both. The shapes must mirror AND the paired values must be equal. [1,2,2,null,3,null,3] is structurally a mirror but the 3s land on the same side, so it is NOT symmetric.
Q2.Can the tree be empty?
The constraint says at least 1 node, but a clean solution treats an empty tree as trivially symmetric (two null children mirror each other).
Q3.Do you want recursive or iterative?
Lead with the recursive mirror helper (cleanest), then offer the iterative BFS version since 'solve it iteratively' is the stated follow-up.
Q4.Could values repeat across the tree?
Yes. That's exactly why a value match alone isn't enough — you must also confirm the mirrored positions line up.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A tree is symmetric when its left and right subtrees are mirror images. Don't traverse one tree — compare two pointers walking in opposite directions: `left.left` against `right.right` and `left.right` against `right.left`. The recursive `isMirror(a, b)` is four lines; the iterative version pairs nodes in a queue and pulls them out two at a time. Both run in O(n) time.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize symmetry as a comparison between two pointers rather than a single traversal, and whether you get the mirror crossing (left.left↔right.right, left.right↔right.left) correct instead of accidentally writing Same Tree.

Where candidates slip

Comparing same-side children (a.left with b.left), which checks whether the subtrees are identical rather than mirrored — passes [1,2,2] but wrongly handles [1,2,2,3,4,4,3] vs structurally-different inputs.

How to stand out

State that this is Same Tree with crossed recursion, then offer the iterative BFS variant unprompted and note both are O(n) time and O(h) / O(w) space respectively.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Mirror Comparison	`O(n)`	`O(h)`	Start here. Frame it as 'compare two pointers walking in opposite directions' — that one sentence is what the interviewer wants to hear.	Read
2	Iterative BFS with a Queue of PairsOptimal	`O(n)`	`O(w)`	Offer it when the interviewer says 'now do it without recursion', or to preempt the follow-up. Emphasize you enqueue nodes in mirror order.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCompare two subtreesShould they be identical or mirrored?IdenticalMirroredExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive Mirror Comparison

TimeO(n)SpaceO(h)

Start here. Frame it as 'compare two pointers walking in opposite directions' — that one sentence is what the interviewer wants to hear.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Symmetry is about the left subtree reflecting the right. So you're really comparing TWO trees, not inspecting one. What two nodes should you start the comparison with?

2Hint 2Explore hint

Write a helper isMirror(a, b). When are two nodes a valid mirror pair? Their values must match, and their children must mirror — but which child of a pairs with which child of b?

3Hint 3Explore hint

The outer edges pair up and the inner edges pair up: a.left mirrors b.right, and a.right mirrors b.left. Recurse on those two crossed pairs.

A · Core idea

The reframe that unlocks this problem: symmetry is not a property you can read off a single node, it's a relationship between two subtrees. So we throw away the instinct to traverse root and instead launch a comparison of root.left against root.right, asking at every step 'are these two nodes a valid mirror pair?'

The base cases come first, and order matters. Two null nodes are a valid mirror pair — two missing subtrees reflect each other perfectly, so return true. If exactly one is null, the shapes already disagree, so return false. Checking both-null before one-null is what prevents you from dereferencing a node that doesn't exist; flip them and you'd ask a.val on a null a.

The crossing is the entire algorithm. Once both nodes exist, their values must be equal, and then — here is the only line people get wrong — the outer children must mirror and the inner children must mirror. Concretely a.left pairs with b.right (the two outermost branches) and a.right pairs with b.left (the two innermost branches). If you instead recurse on a.left vs b.left, you've written Same Tree: you'd be checking whether the two subtrees are identical, not reflected. They happen to give the same answer on a fully balanced value set, which is exactly why the bug survives shallow testing and then fails on the classic [1,2,2,null,3,null,3].

Why a value match alone isn't enough. Equality of a.val and b.val is necessary but not sufficient — the structure underneath has to mirror too. That's why the return statement is a conjunction: value equality && outer mirror && inner mirror. Short-circuit evaluation means the moment any pair disagrees, the whole recursion collapses back to false without exploring the rest.

Why O(n) is the floor. To certify symmetry you must inspect every node — a single mismatched leaf buried deep can break it — so no algorithm can do better than linear time. The only axis left to optimize is space, which the iterative variant trades from implicit call stack to an explicit queue.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,2,3,4,4,3]

Interactive diagram

The example tree [1,2,2,3,4,4,3]

isMirror(2, 2)

Active call / nodeSupporting contextReturned stateNot active

Dashed lines show the mirror pairs: 2↔2, then outer 3↔3 and inner 4↔4.

Final resulttrue

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the full code

solution.javaJava

Recursive Mirror Comparison — reference

4 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public boolean isSymmetric(TreeNode root) {
10
    if (root == null) return true;
11
    return isMirror(root.left, root.right);
12
}
13
 
14
private boolean isMirror(TreeNode a, TreeNode b) {
15
    if (a == null && b == null) return true;   // both empty → mirror
16
    if (a == null || b == null) return false;  // exactly one empty → not
17
    return a.val == b.val
18
        && isMirror(a.left, b.right)           // outer pair
19
        && isMirror(a.right, b.left);          // inner pair
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

Symmetric Tree is literally Same Tree with the recursion crossed. If you've memorized isSameTree, you get this for free by swapping the second recursive call's argument from b.left to b.right and b.right to b.left. Saying that out loud signals you see the shared skeleton beneath both problems.

ComplexityO(n) time, O(h) space — Each node is visited at most once as part of exactly one mirror pair, so the work is O(n). The recursion depth equals the tree height h → O(h) call-stack space, O(log n) balanced and O(n) for a degenerate tree.

E · Edge cases and pitfalls4Recursing on a.left vs b.left (same side) — that's Same Tree, not symmetry.Explore edge cases

Pitfalls

Recursing on a.left vs b.left (same side) — that's Same Tree, not symmetry.
Checking one-null before both-null, causing a null dereference.
Returning only a.val == b.val without recursing — value match is necessary but not sufficient.
Trying to invert the tree and compare to the original — wasteful and mutates input; the two-pointer compare is cleaner.

03.2

Approach 2 of 2 · Optimal

Iterative BFS with a Queue of Pairs

TimeO(n)SpaceO(w)

Offer it when the interviewer says 'now do it without recursion', or to preempt the follow-up. Emphasize you enqueue nodes in mirror order.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Recursion uses the call stack to remember which pairs still need comparing. To remove recursion, store those pairs yourself — in what structure, and what do you store in it?

2Hint 2Explore hint

Use a queue (or stack) of NODES, but enqueue them in mirror order so that when you pull two out, they're the pair to compare.

3Hint 3Explore hint

Each iteration dequeues two nodes a and b, checks the same base cases and value equality, then enqueues the outer pair (a.left, b.right) and inner pair (a.right, b.left).

A · Core idea

The recursive solution leans on the language runtime's call stack to remember which mirror pairs are still outstanding. The iterative version makes that bookkeeping explicit with a queue, which is the standard answer to 'solve it without recursion' and also sidesteps stack-overflow on pathologically deep trees.

The key idea is to enqueue in mirror order. We seed the queue with root.left and root.right. Then each loop turn pulls two nodes — a and b — that are supposed to be a mirror pair. We run exactly the same checks as the recursion: both null is fine and we continue; one null means asymmetry and we return false; unequal values mean asymmetry. If they pass, we push the next pairs to compare — and the order we push them in is everything.

Why the push order is (a.left, b.right, a.right, b.left). Because we dequeue two at a time, the pairing is determined entirely by insertion order. Pushing a.left then b.right means the next-but-one dequeue yields exactly that outer pair; pushing a.right then b.left queues up the inner pair. Get this order wrong and you'll silently compare the wrong nodes — the iterative analog of the same-side bug in the recursion.

Why a queue and a stack both work. The comparison is order-independent across pairs: a tree is symmetric only if every pair matches, so it doesn't matter whether we process pairs breadth-first (queue) or depth-first (stack). People reach for a queue out of habit, but swapping ArrayDeque.poll/offer for push/pop changes nothing about correctness. The only observable difference is the traversal order and thus the peak container size.

Space trade-off worth stating. Recursion costs O(h); BFS costs O(w), the maximum level width. On a deep, skinny tree the iterative version actually uses less peak memory and avoids stack overflow; on a wide, shallow tree recursion wins. Mentioning this trade-off — rather than claiming one is universally better — is what separates a memorized answer from understanding.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,2,null,3,null,3]

Interactive diagram

Mirror check vs sameness check

seed

Active call / nodeSupporting contextReturned stateNot active

The decision that trips up most candidates: symmetry crosses the recursion, Same Tree does not.

Final resultfalse

C · Code with teaching comments

solution.javaJava

Iterative BFS with a Queue of Pairs — optimal

5 teaching notes

1
public boolean isSymmetric(TreeNode root) {
2
    if (root == null) return true;
3
    Deque<TreeNode> queue = new ArrayDeque<>();
4
    // Seed with the two subtrees that must mirror — left and right of the root.
5
    queue.offer(root.left);
6
    queue.offer(root.right);
7
    while (!queue.isEmpty()) {
8
        // Pull the two halves of a mirror pair out together — the second poll on the
9
        // next line completes the pair.
10
        TreeNode a = queue.poll();
11
        TreeNode b = queue.poll();
12
        if (a == null && b == null) continue;       // matched empties
13
        if (a == null || b == null) return false;   // shape mismatch
14
        if (a.val != b.val) return false;           // value mismatch
15
        queue.offer(a.left);                          // outer pair...
16
        queue.offer(b.right);
17
        queue.offer(a.right);                         // inner pair...
18
        // Completes the inner pair (a.right, b.left). The four offers per iteration are
19
        // the iterative form of the two crossed recursive calls.
20
        queue.offer(b.left);
21
    }
22
    return true;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(w) spaceOpen the invariant and proofExplore the proof

The whole iterative trick is 'enqueue in the order you'd recurse'. Because we dequeue pairs, the insertion sequence (outer-a, outer-b, inner-a, inner-b) hard-codes the mirror crossing into the data structure instead of into recursive call arguments. Same logic, relocated from the stack frame to the queue.

ComplexityO(n) time, O(w) space — Every node enters and leaves the queue once → O(n) time. The queue holds at most one level's worth of node pairs, so its size is bounded by the tree width w → O(w) space, which is O(n) in the worst (bottom-heavy) level but typically less than the recursion's O(h) on skewed trees.

E · Edge cases and pitfalls7root = [1] — Seed queue with (null, null); first iteration both-null → continue, queue empties → return true.Explore edge cases

Edge cases handled

root = [1]Seed queue with (null, null); first iteration both-null → continue, queue empties → return true.
root = [1,2,2,2,null,2]Outer pair (2,2) ok, but then a one-null pair appears → return false. Tests that value match alone doesn't save an asymmetric shape.
Large balanced treeQueue width peaks at the widest level (~n/2 nodes), so peak space is O(n) here but the algorithm short-circuits the instant any pair mismatches.

Pitfalls

Enqueuing in same-side order (a.left, b.left, ...) — reproduces the Same Tree bug.
Polling only one node per iteration instead of two — breaks the pair invariant.
Forgetting the both-null `continue`, then dereferencing null on the value check.
Assuming a queue is required — a stack works identically since all pairs must match.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic boolean isSymmetric(TreeNode root) { if (root == null) return true; Deque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root.left); queue.offer(root.right);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Same-side recursion (writing Same Tree by accident)

Symmetry requires crossing the children. Recursing a.left vs b.left and a.right vs b.right tests whether the two subtrees are identical, not mirrored. It passes balanced inputs but fails cases like [1,2,2,null,3,null,3].

Explore the code comparison

Don't write this

return a.val == b.val
    && isMirror(a.left, b.left)
    && isMirror(a.right, b.right);

Write this instead

return a.val == b.val
    && isMirror(a.left, b.right)
    && isMirror(a.right, b.left);

Null checks in the wrong order

If you test 'exactly one null' before 'both null', the both-null case is fine — but reversing it the other way and then accessing a.val before any null check dereferences a missing node.

Explore the code comparison

Don't write this

def is_mirror(a, b):
    if a.val != b.val:        # crashes when a or b is None
        return False
    return is_mirror(a.left, b.right) and is_mirror(a.right, b.left)

Write this instead

def is_mirror(a, b):
    if a is None and b is None:
        return True
    if a is None or b is None:
        return False
    return (a.val == b.val
            and is_mirror(a.left, b.right)
            and is_mirror(a.right, b.left))

Wrong enqueue order in the iterative version

Because nodes are dequeued two at a time, the insertion order defines the pairing. Pushing same-side children means you later compare a.left with b.left — the iterative form of the Same Tree bug.

Explore the code comparison

Don't write this

queue.offer(a.left);
queue.offer(b.left);
queue.offer(a.right);
queue.offer(b.right);

Write this instead

queue.offer(a.left);
queue.offer(b.right);
queue.offer(a.right);
queue.offer(b.left);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Mirror comparison of two subtrees (outer-vs-outer, inner-vs-inner)

Code pattern to memorize

isMirror(a, b):
    if a == null and b == null: return true
    if a == null or  b == null: return false
    return a.val == b.val
        and isMirror(a.left,  b.right)   # outer pair
        and isMirror(a.right, b.left)    # inner pair

Rules to remember

1Symmetry is a two-tree problem, not a one-tree traversal — compare root.left with root.right, never root with itself.
2The mirror crossing is the whole trick: pair a.left with `b.right` and a.right with `b.left`. Pairing same-side children silently tests sameness, not symmetry.
3Handle the both-null base case before the one-null case, or you dereference a missing child.
4Compare a.val == b.val and recurse — a value match alone is necessary but not sufficient.
5The iterative form enqueues nodes in mirror order (a.left, b.right, a.right, b.left) and dequeues them in pairs.

Use this pattern when

Asked whether a tree is a mirror of itself around the center
You need to compare two structures position-by-position in reverse
Any 'is this palindromic / reflected' question on a tree shape
Follow-up to Same Tree where one side is flipped

Choose another pattern when

You only have one subtree to inspect → that's a plain traversal, not a mirror check
Order doesn't matter, only the set of values → sort/compare multisets instead
You need the mirrored *tree* as output, not a boolean → that's Invert Binary Tree
Comparison is structural-identical, not reflected → that's Same Tree (a.left vs b.left)

Interview takeaway

Symmetric Tree is Same Tree with a twist: instead of comparing matching sides, you compare crossed sides. Internalize that mirror means outer-with-outer and inner-with-inner, and the entire family of mirror/reflection problems collapses into one four-line helper.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTwo-pointer mirror comparison on a tree. Recognise it whenever you must verify a reflected/palindromic relationship between two subtrees. It's the crossed-recursion cousin of Same Tree, and the same isMirror/isSame helper underlies Subtree of Another Tree and Flip Equivalent Binary Trees.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same Tree
The non-crossed sibling of this problem — compare a.left with b.left and a.right with b.right.
Invert Binary Tree
Produces the mirror tree as output; a symmetric tree equals its own inversion.
Flip Equivalent Binary Trees
Coming soon
Generalizes the crossing — at each node, try both the matched and the flipped pairing.
Subtree of Another Tree
Reuses the same-tree comparison helper as a building block while scanning every node.

Same pattern

←

Sum Root to Leaf Numbers

Continue · Next problem

Lowest Common Ancestor with Binary Lifting

easyTreesLC #101Frequently asked

Symmetric Tree

LCPractice

Trees & BST · 22 of 41 · 9 min

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

A tree is symmetric if the left subtree is a mirror reflection of the right subtree: the structures match and the values match when one side is read left-to-right and the other right-to-left.

In plain English

Examples

Example 1

Input: root = [1,2,2,3,4,4,3]
Output: true
Note: Left subtree is (2 → 3,4), right subtree is (2 → 4,3). Reading the right side in reverse gives 3,4 — a perfect mirror of the left.

Example 2

Input: root = [1,2,2,null,3,null,3]
Output: false
Note: Both 2s have a single child, but the left's child is on the right and the right's child is also on the right. They don't mirror — the 3s should land on opposite sides.

Example 3

Input: root = [1]
Output: true
Note: A single node has two empty subtrees, which trivially mirror each other.

Constraints

The number of nodes is in the range [1, 1000]
-100 ≤ Node.val ≤ 100
Follow-up: solve it both recursively and iteratively

Clarifying questions4First question: Does symmetry require matching values, or only matching structure?Explore questions

Q1.Does symmetry require matching values, or only matching structure?
Both. The shapes must mirror AND the paired values must be equal. [1,2,2,null,3,null,3] is structurally a mirror but the 3s land on the same side, so it is NOT symmetric.
Q2.Can the tree be empty?
The constraint says at least 1 node, but a clean solution treats an empty tree as trivially symmetric (two null children mirror each other).
Q3.Do you want recursive or iterative?
Lead with the recursive mirror helper (cleanest), then offer the iterative BFS version since 'solve it iteratively' is the stated follow-up.
Q4.Could values repeat across the tree?
Yes. That's exactly why a value match alone isn't enough — you must also confirm the mirrored positions line up.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

How to stand out

State that this is Same Tree with crossed recursion, then offer the iterative BFS variant unprompted and note both are O(n) time and O(h) / O(w) space respectively.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Recursive Mirror Comparison	`O(n)`	`O(h)`	Start here. Frame it as 'compare two pointers walking in opposite directions' — that one sentence is what the interviewer wants to hear.	Read
2	Iterative BFS with a Queue of PairsOptimal	`O(n)`	`O(w)`	Offer it when the interviewer says 'now do it without recursion', or to preempt the follow-up. Emphasize you enqueue nodes in mirror order.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Recursive Mirror Comparison

TimeO(n)SpaceO(h)

Start here. Frame it as 'compare two pointers walking in opposite directions' — that one sentence is what the interviewer wants to hear.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Symmetry is about the left subtree reflecting the right. So you're really comparing TWO trees, not inspecting one. What two nodes should you start the comparison with?

2Hint 2Explore hint

Write a helper isMirror(a, b). When are two nodes a valid mirror pair? Their values must match, and their children must mirror — but which child of a pairs with which child of b?

3Hint 3Explore hint

The outer edges pair up and the inner edges pair up: a.left mirrors b.right, and a.right mirrors b.left. Recurse on those two crossed pairs.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,2,3,4,4,3]

Interactive diagram

The example tree [1,2,2,3,4,4,3]

isMirror(2, 2)

Active call / nodeSupporting contextReturned stateNot active

Dashed lines show the mirror pairs: 2↔2, then outer 3↔3 and inner 4↔4.

Final resulttrue

C · Code with teaching comments

Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the full code

solution.javaJava

Recursive Mirror Comparison — reference

4 teaching notes

1
// Definition for a binary tree node.
2
class TreeNode {
3
    int val;
4
    TreeNode left;
5
    TreeNode right;
6
    TreeNode(int val) { this.val = val; }
7
}
8
 
9
public boolean isSymmetric(TreeNode root) {
10
    if (root == null) return true;
11
    return isMirror(root.left, root.right);
12
}
13
 
14
private boolean isMirror(TreeNode a, TreeNode b) {
15
    if (a == null && b == null) return true;   // both empty → mirror
16
    if (a == null || b == null) return false;  // exactly one empty → not
17
    return a.val == b.val
18
        && isMirror(a.left, b.right)           // outer pair
19
        && isMirror(a.right, b.left);          // inner pair
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls4Recursing on a.left vs b.left (same side) — that's Same Tree, not symmetry.Explore edge cases

Pitfalls

Recursing on a.left vs b.left (same side) — that's Same Tree, not symmetry.
Checking one-null before both-null, causing a null dereference.
Returning only a.val == b.val without recursing — value match is necessary but not sufficient.
Trying to invert the tree and compare to the original — wasteful and mutates input; the two-pointer compare is cleaner.

03.2

Approach 2 of 2 · Optimal

Iterative BFS with a Queue of Pairs

TimeO(n)SpaceO(w)

Offer it when the interviewer says 'now do it without recursion', or to preempt the follow-up. Emphasize you enqueue nodes in mirror order.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Recursion uses the call stack to remember which pairs still need comparing. To remove recursion, store those pairs yourself — in what structure, and what do you store in it?

2Hint 2Explore hint

Use a queue (or stack) of NODES, but enqueue them in mirror order so that when you pull two out, they're the pair to compare.

3Hint 3Explore hint

Each iteration dequeues two nodes a and b, checks the same base cases and value equality, then enqueues the outer pair (a.left, b.right) and inner pair (a.right, b.left).

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

root = [1,2,2,null,3,null,3]

Interactive diagram

Mirror check vs sameness check

seed

Active call / nodeSupporting contextReturned stateNot active

The decision that trips up most candidates: symmetry crosses the recursion, Same Tree does not.

Final resultfalse

C · Code with teaching comments

solution.javaJava

Iterative BFS with a Queue of Pairs — optimal

5 teaching notes

1
public boolean isSymmetric(TreeNode root) {
2
    if (root == null) return true;
3
    Deque<TreeNode> queue = new ArrayDeque<>();
4
    // Seed with the two subtrees that must mirror — left and right of the root.
5
    queue.offer(root.left);
6
    queue.offer(root.right);
7
    while (!queue.isEmpty()) {
8
        // Pull the two halves of a mirror pair out together — the second poll on the
9
        // next line completes the pair.
10
        TreeNode a = queue.poll();
11
        TreeNode b = queue.poll();
12
        if (a == null && b == null) continue;       // matched empties
13
        if (a == null || b == null) return false;   // shape mismatch
14
        if (a.val != b.val) return false;           // value mismatch
15
        queue.offer(a.left);                          // outer pair...
16
        queue.offer(b.right);
17
        queue.offer(a.right);                         // inner pair...
18
        // Completes the inner pair (a.right, b.left). The four offers per iteration are
19
        // the iterative form of the two crossed recursive calls.
20
        queue.offer(b.left);
21
    }
22
    return true;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(w) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7root = [1] — Seed queue with (null, null); first iteration both-null → continue, queue empties → return true.Explore edge cases

Edge cases handled

root = [1]Seed queue with (null, null); first iteration both-null → continue, queue empties → return true.
root = [1,2,2,2,null,2]Outer pair (2,2) ok, but then a one-null pair appears → return false. Tests that value match alone doesn't save an asymmetric shape.
Large balanced treeQueue width peaks at the widest level (~n/2 nodes), so peak space is O(n) here but the algorithm short-circuits the instant any pair mismatches.

Pitfalls

Enqueuing in same-side order (a.left, b.left, ...) — reproduces the Same Tree bug.
Polling only one node per iteration instead of two — breaks the pair invariant.
Forgetting the both-null `continue`, then dereferencing null on the value check.
Assuming a queue is required — a stack works identically since all pairs must match.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Same-side recursion (writing Same Tree by accident)

Explore the code comparison

Don't write this

return a.val == b.val
    && isMirror(a.left, b.left)
    && isMirror(a.right, b.right);

Write this instead

return a.val == b.val
    && isMirror(a.left, b.right)
    && isMirror(a.right, b.left);

Null checks in the wrong order

If you test 'exactly one null' before 'both null', the both-null case is fine — but reversing it the other way and then accessing a.val before any null check dereferences a missing node.

Explore the code comparison

Don't write this

def is_mirror(a, b):
    if a.val != b.val:        # crashes when a or b is None
        return False
    return is_mirror(a.left, b.right) and is_mirror(a.right, b.left)

Write this instead

def is_mirror(a, b):
    if a is None and b is None:
        return True
    if a is None or b is None:
        return False
    return (a.val == b.val
            and is_mirror(a.left, b.right)
            and is_mirror(a.right, b.left))

Wrong enqueue order in the iterative version

Because nodes are dequeued two at a time, the insertion order defines the pairing. Pushing same-side children means you later compare a.left with b.left — the iterative form of the Same Tree bug.

Explore the code comparison

Don't write this

queue.offer(a.left);
queue.offer(b.left);
queue.offer(a.right);
queue.offer(b.right);

Write this instead

queue.offer(a.left);
queue.offer(b.right);
queue.offer(a.right);
queue.offer(b.left);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Mirror comparison of two subtrees (outer-vs-outer, inner-vs-inner)

Code pattern to memorize

isMirror(a, b):
    if a == null and b == null: return true
    if a == null or  b == null: return false
    return a.val == b.val
        and isMirror(a.left,  b.right)   # outer pair
        and isMirror(a.right, b.left)    # inner pair

Rules to remember

1Symmetry is a two-tree problem, not a one-tree traversal — compare root.left with root.right, never root with itself.
2The mirror crossing is the whole trick: pair a.left with `b.right` and a.right with `b.left`. Pairing same-side children silently tests sameness, not symmetry.
3Handle the both-null base case before the one-null case, or you dereference a missing child.
4Compare a.val == b.val and recurse — a value match alone is necessary but not sufficient.
5The iterative form enqueues nodes in mirror order (a.left, b.right, a.right, b.left) and dequeues them in pairs.

Use this pattern when

Asked whether a tree is a mirror of itself around the center
You need to compare two structures position-by-position in reverse
Any 'is this palindromic / reflected' question on a tree shape
Follow-up to Same Tree where one side is flipped

Choose another pattern when

You only have one subtree to inspect → that's a plain traversal, not a mirror check
Order doesn't matter, only the set of values → sort/compare multisets instead
You need the mirrored *tree* as output, not a boolean → that's Invert Binary Tree
Comparison is structural-identical, not reflected → that's Same Tree (a.left vs b.left)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same Tree
The non-crossed sibling of this problem — compare a.left with b.left and a.right with b.right.
Invert Binary Tree
Produces the mirror tree as output; a symmetric tree equals its own inversion.
Flip Equivalent Binary Trees
Coming soon
Generalizes the crossing — at each node, try both the matched and the flipped pairing.
Subtree of Another Tree
Reuses the same-tree comparison helper as a building block while scanning every node.

Same pattern

←

Sum Root to Leaf Numbers

Continue · Next problem

Lowest Common Ancestor with Binary Lifting