Trees · LC #101
Symmetric Tree
Check whether a binary tree is a mirror of itself around its center axis. Reframe as: are the left and right subtrees mirrors of each other?
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Sample I/O
Input: [1,2,2,3,4,4,3] Output: true Input: [1,2,2,null,3,null,3] Output: false
Time: O(n) · Space: O(h)
Intuition
How to Think About It
Intuition
Recursion works because symmetry is defined recursively: a tree is symmetric iff its left subtree is a mirror of its right subtree. Two subtrees are mirrors iff they have equal root values, the left's left mirrors the right's right, and the left's right mirrors the right's left - a cross-comparison pattern.
Core Concept
Define a helper `isMirror(l, r)`: both null → true; one null → false; values differ → false; recurse as `isMirror(l.left, r.right) && isMirror(l.right, r.left)`. Call `isMirror(root.left, root.right)` at the top level.
When to use
Symmetry checks, palindrome-structure problems on trees, validating mirror configurations.
When NOT to use
When you only need value symmetry (same multiset) without caring about structural position.
Key Insights
What to Know Cold
- Cross-comparison: l.left vs r.right and l.right vs r.left - not same-side.
- Same logic as isSameTree but with mirrored child arguments.
- Iterative BFS: use a queue, enqueue pairs (l.left, r.right) and (l.right, r.left).
- A single-node tree is always symmetric.
- An empty tree is symmetric by convention.
2 examples
Worked Examples
Symmetric tree
[1,2,2,3,4,4,3] - values mirror around the center.
isMirror(2,2): values match. isMirror(3,3): match. isMirror(4,4): match. All true.
function isSymmetric(root: TreeNode | null): boolean {
function mirror(l: TreeNode|null, r: TreeNode|null): boolean {
if (!l && !r) return true;
if (!l || !r || l.val !== r.val) return false;
return mirror(l.left, r.right) && mirror(l.right, r.left);
}
return mirror(root?.left ?? null, root?.right ?? null);
}Output: true
Illustrates cross-pairing pattern - the key distinction from isSameTree.
Asymmetric tree
[1,2,2,null,3,null,3] - null positions don't mirror.
isMirror(2,2): match. isMirror(null, null): true. isMirror(3, null): one null → false.
Output: false
Null placement asymmetry is a common edge case in structural checks.