AlgoMaster Logo

Symmetric Tree

easyFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We need to determine if a binary tree is a mirror image of itself. Fold the tree along the vertical line through the root. If the left half overlaps the right half, the tree is symmetric.

The mirror condition is defined on the two subtrees of the root: the left subtree and the right subtree must be reflections of each other. For two subtrees to be mirrors:

  • Their root values must be equal.
  • The left child of one must mirror the right child of the other, and vice versa.

This differs from checking whether the two subtrees are identical. Identical means structurally the same. Mirror means one is the flipped version of the other. So we compare the left child of the left subtree with the right child of the right subtree, and the right child of the left subtree with the left child of the right subtree.

Key Constraints:

  • Number of nodes in [1, 1000] → The tree is small, but since we must inspect every node at least once to confirm symmetry, O(n) is the target.
  • -100 <= Node.val <= 100 → Node values are small integers, so equality comparison carries no overflow risk.
  • At least 1 node → The tree is never empty. The null-root check below is defensive rather than required by the constraints.

Approach 1: Recursive DFS

Intuition

The mirror condition is recursive. A tree is symmetric if its left subtree is a mirror of its right subtree, and two subtrees are mirrors of each other if:

  1. Their root values are the same.
  2. The left child of one mirrors the right child of the other.
  3. The right child of one mirrors the left child of the other.

This maps directly to a helper isMirror(left, right) that checks whether two subtrees are mirrors. We call it once with isMirror(root.left, root.right), and conditions 2 and 3 generate the recursive calls.

The base cases close the recursion. If both nodes are null, they are mirrors (two empty subtrees are reflections of each other). If exactly one is null, the structures differ, so they cannot be mirrors. If their values differ, they are not mirrors. Otherwise, we recurse on the cross-paired children.

Algorithm

  1. If root is null, return true (an empty tree is symmetric).
  2. Call the helper isMirror(root.left, root.right).
  3. In isMirror(left, right):
    • If both left and right are null, return true.
    • If only one is null, return false.
    • If left.val does not equal right.val, return false.
    • Recursively check isMirror(left.left, right.right) AND isMirror(left.right, right.left).
  4. Return the result.

Example Walkthrough

1Start: call isMirror(left=node2, right=node2)
1root2left342right43
1/6

Code

The recursion is optimal in time but relies on the call stack, which can overflow on a deeply skewed tree. The next approach replaces the call stack with an explicit queue.

Approach 2: Iterative BFS with Queue

Intuition

This approach runs the same comparison as the recursion, but manages the pending work in a queue instead of the call stack.

We enqueue the root's left and right children as a pair. Then we process pairs one at a time: dequeue two nodes, check whether they form a valid mirror at this position, and if so, enqueue their children in mirror order. A mismatch returns false immediately. If every pair matches, the tree is symmetric.

Algorithm

  1. If root is null, return true.
  2. Create a queue. Enqueue root.left and root.right as the first pair.
  3. While the queue is not empty:
    • Dequeue two nodes (left and right).
    • If both are null, continue to the next pair.
    • If only one is null, or their values differ, return false.
    • Enqueue left.left and right.right (outer pair).
    • Enqueue left.right and right.left (inner pair).
  4. Return true (all pairs matched).

Example Walkthrough

This trace uses the asymmetric tree [1, 2, 2, null, 3, null, 3] to show how the queue detects a mismatch and stops early.

1Enqueue first pair: (left=2, right=2)
1root2left32right3
1/4

Code