Mirror-Image Check
EasyTrees
Problem
A logo designer stores ornaments as binary trees and wants to know which ones look the same in a mirror held along the vertical axis through the root.
Given the root, return true if the left half of the tree is the mirror image of the right half (shape and values), false otherwise.
Example 1
- Input:
- root = [1, 2, 2, 3, 4, 4, 3]
- Output:
- true
Outer pairs (3, 3) and inner pairs (4, 4) match across the axis.
Example 2
- Input:
- root = [1, 2, 2, null, 3, null, 3]
- Output:
- false
Both 3s hang to the right, so they do not mirror each other.
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -100 ≤ node.val ≤ 100
Hint
Show the first hint
Symmetry compares two subtrees against each other, not a subtree against itself.
Walkthrough
How to approach it
01Clarify before coding
- Is an empty tree symmetric? Yes.
- Do values matter or only shape? Both.
- Is a single node symmetric? Yes, both halves are empty.
02Brute force
Build a mirrored copy of the whole tree, then check whether the copy equals the original.
Cost: O(n) time but O(n) extra memory for the copy, and it inspects every node twice.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.