Symmetric Tree
Check whether a binary tree is a mirror of itself by comparing mirror pairs through a queue: outer children with outer, inner with inner.
Problem Understanding
Symmetric Tree: given the root of a binary tree, check whether it is a mirror of itself, symmetric around its centre.
Example: [1, 2, 2, 3, 4, 4, 3] is symmetric; [1, 2, 2, null, 3, null, 3] is not, because both 3s hang on the right.
The Intuition: Compare Crosswise
Fold the tree down the middle. Every node on the left must land on a node with the same value on the right. So compare pairs:
- Start with
(root.left, root.right). - Two nulls are a match; one null or two different values break the mirror.
- A matching pair
(a, b)passes the check down crosswise: the outer pair(a.left, b.right)and the inner pair(a.right, b.left).
Processing the pairs with a queue is the same breadth-first search loop as Binary Tree Level Order Traversal, but each queue entry holds two nodes instead of one.
Interactive Walkthrough
The two nodes being compared light up together, one on each side, and matched nodes turn green. The queue of pairs is listed beside the tree. Try Example 2, where the levels look symmetric but the structure is not.
Dry Run Table
Input: root = [1, 2, 2, 3, 4, 4, 3]
| Pair | Result | Queued |
|---|---|---|
| (2, 2) | match | (3, 3), (4, 4) |
| (3, 3) | match | (null, null) × 2 |
| (4, 4) | match | (null, null) × 2 |
| (null, null) × 4 | skip | — |
The queue empties. Answer: true.
The Solution Template
A queue of node pairs. LeetCode guarantees at least one node, so root is never null.
Symmetric Tree Code
1var isSymmetric = function(root) {2 const queue = [[root.left, root.right]];3 let head = 0;4 while (head < queue.length) {5 const [a, b] = queue[head++];6 if (!a && !b) continue;7 if (!a || !b || a.val !== b.val) return false;8 queue.push([a.left, b.right]);9 queue.push([a.right, b.left]);10 }11 return true;12};
Edge Cases & Common Mistakes
- One node: both children are null, so the first pair is skipped and the answer is true.
- Comparing the same side: pairing
(a.left, b.left)checks for identical subtrees, not mirrors; always pair crosswise. - Ignoring nulls:
[1, 2, 2, null, 3, null, 3]only fails because a null meets a 3; nulls are part of the shape. - Checking values only per level: a palindromic level is necessary but not sufficient without null placeholders.
- Recursion depth: a deep skewed tree can hit recursion limits; the queue version avoids that.
Summary
Queue the pair (root.left, root.right). For each pair, two nulls match, one null or different values mean false, and a matching pair queues its outer and inner children crosswise. If the queue empties, the tree is symmetric. O(n) time, O(w) space.
More practice: DSA interview questions with answers · patterns cheat sheet