Symmetric Tree

Problem summary

Given the root of a binary tree, check whether it is a mirror of itself around its center — that is, the left subtree is a mirror reflection of the right subtree.

    1                  1
   / \                / \
  2   2      vs      2   2
 / \ / \                \  \
3  4 4  3                3  3
symmetric              not symmetric

n is at most 1000, so any traversal that visits each node a constant number of times is fast enough. The real work is figuring out exactly what "mirror" means for two subtrees.

Key idea: compare the tree against its own reflection

A single tree can't check itself for symmetry directly, but two trees can check whether they are mirrors of each other. So split the root's two children into a pair, left = root.left and right = root.right, and ask: is right the mirror image of left?

Two subtrees left and right are mirrors of each other when:

• both are null (an empty mirror is trivially symmetric), or
• both exist, their values match, and
  • left's left child mirrors right's right child, and
  • left's right child mirrors right's left child

Notice the crossed pairing: left.left is compared against right.right, not right.left. That crossing is exactly what "mirror" means — the outer edges of the tree must match each other, and so must the inner edges.

Approach: recursive mirror check

isSymmetric just hands the two children of the root to a helper, isMirror(left, right), that performs the crossed comparison above:

isMirror(left, right):
    if left is null and right is null: return true
    if left is null or right is null:  return false
    return left.val == right.val
       and isMirror(left.left,  right.right)
       and isMirror(left.right, right.left)

An empty tree (root == null) is symmetric by definition, so isSymmetric short-circuits on that before calling the helper.

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }

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

Walkthrough

Take Example 1: root = [1,2,2,3,4,4,3].

        1
       / \
      2   2
     / \ / \
    3  4 4  3

isMirror(2ₗ, 2ᵣ) is called first (the two children of the root):

• values match: 2 == 2
• isMirror(3, 3) — the outer pair — both leaves, values match, no children → true
• isMirror(4, 4) — the inner pair — both leaves, values match, no children → true
• both sides true, so isMirror(2ₗ, 2ᵣ) → true

The whole tree is symmetric → true.

Now Example 2: root = [1,2,2,null,3,null,3].

        1
       / \
      2   2
       \   \
        3   3

isMirror(2ₗ, 2ᵣ) is called:

• values match: 2 == 2
• isMirror(2ₗ.left, 2ᵣ.right) = isMirror(null, 3) — one is null, the other is not → false

The && short-circuits immediately, so the answer is false — even though both 2s happen to have a single child valued 3, those 3s sit on the same side (both are right children), which breaks the mirror.

Follow-up: solving it iteratively

The recursion above is really just doing a BFS/DFS over pairs of nodes. To make it iterative, push pairs onto a queue (or a stack) instead of recursing, and compare each pair as it comes off:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.push(root.left);
        queue.push(root.right);

        while (!queue.isEmpty()) {
            TreeNode left = queue.pop();
            TreeNode right = queue.pop();

            if (left == null && right == null) continue;
            if (left == null || right == null || left.val != right.val) return false;

            // push the outer pair, then the inner pair
            queue.push(left.left);
            queue.push(right.right);
            queue.push(left.right);
            queue.push(right.left);
        }

        return true;
    }
}

The invariant is: the queue always holds an even number of nodes, grouped in pairs that must mirror each other. Any pair that fails the check ends the loop early with false; an empty queue at the end means every pair matched.

Complexity analysis

Time Complexity: O(n)

Every node is visited once, either as part of the recursion or once per queue pop in the iterative version.

Space Complexity: O(n)

The recursive version uses O(h) stack frames for a tree of height h, which is O(n) in the worst case (a skewed tree). The iterative version stores O(n) nodes across the queue/stack in the worst case, since a wide tree can have that many nodes waiting in pairs at once.

Common mistakes

1. Comparing left.left with right.left

That checks whether the two subtrees are identical, not mirrored — the classic "Same Tree" check. Symmetry requires the crossed comparison: left.left against right.right, and left.right against right.left.

2. Forgetting the null cases before touching .val

Both left == null and right == null must be handled before reading left.val or right.val, otherwise a lone missing child throws a null-pointer error instead of correctly returning false.

3. Treating root itself as one of the mirrored pair

The recursion mirrors root.left against root.right — the root itself is the center of symmetry and is never compared to anything. Passing root and root into the helper by mistake will trivially "succeed" without checking anything meaningful.

4. Pushing pairs in the wrong order iteratively

In the iterative version, nodes must be pushed and popped in matching pairs (left/right), and the next generation must be pushed as the crossed pairs (left.left with right.right, left.right with right.left). Pushing them uncrossed silently turns the check into a same-tree check.