Symmetric Tree
Last Updated: March 29, 2026
Understanding the Problem
We need to determine if a binary tree is a mirror image of itself. Picture folding the tree along the vertical line through the root. If the left half perfectly overlaps the right half, the tree is symmetric.
What does "mirror" actually mean here? It means the left subtree of the root and the right subtree of the root are reflections of each other. Specifically, 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 is different from just checking if both subtrees are identical. Identical means structurally the same. Mirror means one is the flipped version of the other. So we're comparing 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]→ With n up to 1,000, even O(n^2) gives us only 1 million operations. But the natural recursive and iterative solutions are both O(n), which is optimal since we need to inspect every node at least once.-100 <= Node.val <= 100→ Node values are small integers. No overflow concerns, and equality comparison is straightforward.At least 1 node→ The tree is never empty. We don't need to handle the null root case, though it's good practice to handle it anyway.
Approach 1: Recursive DFS
Intuition
The most natural way to think about this problem is recursively. A tree is symmetric if its left subtree is a mirror of its right subtree. And two subtrees are mirrors of each other if:
- Their root values are the same.
- The left child of one mirrors the right child of the other.
- The right child of one mirrors the left child of the other.
So we write a helper function isMirror(left, right) that checks whether two subtrees are mirrors. We start by calling isMirror(root.left, root.right), and the recursion takes care of the rest.
The base cases are clean. If both nodes are null, they're mirrors (two empty subtrees are reflections of each other). If exactly one is null, they can't be mirrors. If their values differ, they're not mirrors. Otherwise, we recurse on the cross-paired children.
Algorithm
- If root is null, return true (an empty tree is symmetric).
- Call the helper
isMirror(root.left, root.right). - 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)ANDisMirror(left.right, right.left). - Return the result.
Example Walkthrough
Code
- Time Complexity: O(n). We visit each node exactly once. At each node, we do O(1) work (null checks and value comparison). So the total work is O(n) where n is the number of nodes.
- Space Complexity: O(h), where h is the height of the tree. The space comes from the recursion stack. For a balanced tree, h = O(log n). For a completely skewed tree, h = O(n).
The recursive approach is already optimal in time, but it uses the call stack. What if we wanted to avoid recursion and control the traversal explicitly?
Approach 2: Iterative BFS with Queue
Intuition
Instead of using recursion, we can use a queue to compare mirror pairs iteratively. The idea is the same as the recursive approach, but we manage the "work to do" explicitly with a queue instead of the call stack.
We start by enqueuing the root's left and right children as a pair. Then we process pairs one at a time: dequeue two nodes, check if they're valid mirrors at this level, and if so, enqueue their children in mirror order. If we ever find a mismatch, we return false immediately. If we process all pairs without a mismatch, the tree is symmetric.
The queue processes mirror pairs in breadth-first order. By always enqueuing children in mirror order (left's left with right's right, left's right with right's left), we guarantee that every pair of nodes that should be equal gets compared. The key insight is the enqueue order. We specifically pair the outer children together and the inner children together, which captures the mirror property rather than just structural equality.
Algorithm
- If root is null, return true.
- Create a queue. Enqueue root.left and root.right as the first pair.
- 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).
- Return true (all pairs matched).
Example Walkthrough
Code
- Time Complexity: O(n). Each node is enqueued and dequeued exactly once as part of a pair. At each step, we do O(1) work (null checks, value comparison, enqueue). Total work is O(n).
- Space Complexity: O(n). In the worst case, the queue holds all nodes at the widest level of the tree. For a perfect binary tree, the last level has roughly n/2 nodes.