Given the root of a binary tree, check whether it is a mirror of itself
(i.e., symmetric around its center).
Input: root = [1,2,2,3,4,4,3]
Output: true
Input: root = [1,2,2,null,3,null,3]
Output: false
Constraints:
- 1 <= Number of nodes <= 1000
- -100 <= Node.val <= 100
Contents
- Solution 1 — Recursive
- Solution 2 — Iterative (Queue)
- Complexity Analysis
Recursive
A tree is symmetric if its left subtree is a mirror of its right subtree. Two trees are mirrors if:
- Their roots have the same value.
- The left subtree of one is a mirror of the right subtree of the other.
public boolean isSymmetric(TreeNode root) {
return 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) // outer pair
&& isMirror(left.right, right.left); // inner pair
}
Iterative (Queue)
Enqueue pairs of nodes that should be mirrors. At each step, dequeue a pair and check:
public boolean isSymmetric(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if (left == null && right == null) continue;
if (left == null || right == null) return false;
if (left.val != right.val) return false;
// Enqueue outer pair and inner pair
queue.offer(left.left); queue.offer(right.right);
queue.offer(left.right); queue.offer(right.left);
}
return true;
}
- Time: O(n) — each node is visited once.
- Space: O(n) — queue or call stack proportional to tree size.