#101
Symmetric Tree
Easy Mirror recursion
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether a binary tree is a mirror image of itself around its centre.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: is the tree its own mirror image?
Why this works: compare the left subtree with the right subtree crosswise: outer with outer, inner with inner.
Example: 1 (2 (3, 4), 2 (4, 3))
2 = 2, outer 3 = 3, inner 4 = 4 → symmetric✦Hints open one at a time
Compare the left subtree with the right subtree as mirrors.
Two trees are mirrors if their roots match, a.left mirrors b.right, and a.right mirrors b.left.
↗Approach
Helper mirror(a, b): both null → true; one null → false; else values equal and mirror(a.left, b.right) and mirror(a.right, b.left).
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return mirror(root.left, root.right);
}
private boolean mirror(TreeNode a, TreeNode b) {
if (a == null || b == null) return a == b;
return a.val == b.val && mirror(a.left, b.right) && mirror(a.right, b.left); // outside & inside pairs
}
}!Common mistake
Comparing a.left with b.left — that checks equality, not mirroring.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon