Symmetric Tree
Problem
root of a binary tree, decide whether the tree looks the
same as its mirror image — i.e. folding it along the vertical line through the
root makes the left half land exactly on the right half (same shape, same values).[1,2,2,3,4,4,3]Outputtrue[1,2,2,null,3,null,3]Outputfalse1 ≤ n ≤ 1000 · -100 ≤ Node.val ≤ 100 · Follow-up: solve it both recursively and iteratively.
Try it yourself
class Solution {
public boolean isSymmetric(TreeNode root) {
}
}
a and b are mirrors iff their values match,
a.left mirrors b.right and a.right mirrors
b.left.Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.
Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.
Open the Tree DFS guide →Approaches
Brute ForceBuild the Mirror, then Compare
O(n)Space O(n)A tree is symmetric exactly when it is identical to its own mirror. So build a fresh mirrored copy (swap left/right at every node), then run a standard “same tree” check between the original and the copy.
public boolean isSymmetric(TreeNode root) { return same(root, mirror(root)); } private TreeNode mirror(TreeNode t) { if (t == null) return null; return new TreeNode(t.val, mirror(t.right), mirror(t.left)); } private boolean same(TreeNode a, TreeNode b) { if (a == null || b == null) return a == b; return a.val == b.val && same(a.left, b.left) && same(a.right, b.right); }
Reuses two well-known routines, but allocates a full copy of the tree.
BetterIterative BFS on Node Pairs
O(n)Space O(w)Push the pair (root.left, root.right) into a queue. Pop two nodes:
both null → fine; one null or values differ → not symmetric. Otherwise
enqueue the outer pair (a.left, b.right) and the inner pair
(a.right, b.left). No copy is built.
public boolean isSymmetric(TreeNode root) { if (root == null) return true; Queue<TreeNode> q = new LinkedList<>(); // LinkedList allows nulls q.add(root.left); q.add(root.right); while (!q.isEmpty()) { TreeNode a = q.poll(), b = q.poll(); if (a == null && b == null) continue; if (a == null || b == null || a.val != b.val) return false; q.add(a.left); q.add(b.right); // outer pair q.add(a.right); q.add(b.left); // inner pair } return true; }
No extra tree and no recursion; queue holds up to one level (w = max width).
OptimalRecursive Mirror Check
O(n)Space O(h)Same pair logic, written as recursion: isMirror(a, b) checks the
roots and then the outer and inner pairs. Each node is visited once, and the only
memory is the call stack, bounded by the height h.
public boolean isSymmetric(TreeNode root) { return root == null || isMirror(root.left, root.right); } private boolean isMirror(TreeNode a, TreeNode b) { if (a == null && b == null) return true; if (a == null || b == null) return false; return a.val == b.val && isMirror(a.left, b.right) // outer pair && isMirror(a.right, b.left); // inner pair }
Shortest, clearest code; O(h) stack (O(log n) balanced, O(n) skewed).
&& stops at the first mismatch, so an
asymmetric tree is usually rejected long before all nodes are visited.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Build the Mirror, then Compare | O(n) | O(n) |
| Better | Iterative BFS on Node Pairs | O(n) | O(w) |
| Optimal | Recursive Mirror Check | O(n) | O(h) |
- Comparing
a.leftwithb.left— that checks equality, not mirroring. - Checking only values level by level —
[1,2,2,null,3,null,3]has palindromic values but wrong shape. - Using
ArrayDequefor the queue — it throws onnull; useLinkedList.
- Say the mirror rule out loud: values equal, outer pair mirrors, inner pair mirrors.
- Offer both recursive and iterative versions — it is the stated follow-up.
- Test aloud on a single node, a two-level tree and a shape-only mismatch.