Symmetric Tree
Asked at Google, Meta, Amazon, Microsoft, Apple
Problem
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Meta | Easy | View all Meta questions → |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Apple | Easy | View all Apple questions → |
How to Think About It
The tree is symmetric if the left subtree is a mirror of the right subtree. Compare them as mirrors, not as identical trees.
Mirror comparison: left.left vs right.right (outer nodes), and left.right vs right.left (inner nodes). This is different from same-tree comparison.
Recursive helper: mirror(l, r) checks if two nodes are mirrors. Both null → true. One null → false. Values differ → false. Otherwise recurse: mirror(l.left, r.right) AND mirror(l.right, r.left).
Visual walkthrough for tree: 1
/ \n 2 2
/ / \n 3 4 4 3
mirror(2, 2): values match.
mirror(3, 3): outer pair. Both leaves. true.
mirror(4, 4): inner pair. Both leaves. true.
Result: true.
For tree: 1
/ \n 2 2
/ / \n 3 4 3 4
mirror(2, 2): values match.
mirror(3, 3): outer pair. Both leaves. true.
mirror(4, 4): inner pair. Values match. true.
Wait — mirror(l.left, r.right) = mirror(3, 4). Values differ! False.
Edge cases: empty tree (symmetric), single node (symmetric), one child each side (check values).
Optimal Approach
Step 1: If root is null, return true.
Step 2: Call helper mirror(root.left, root.right).
Step 3: mirror(l, r):
- Both
null→true - One
null→false - Values differ →
false - Return mirror(l.left, r.right) AND mirror(l.right, r.left)
The key difference from same-tree: you compare l.left with r.right (outer) and l.right with r.left (inner). This is mirror comparison, not direct comparison.
Time: O(n). Space: O(h).
What Trips People Up in Real Interviews
Confusing this with "same tree." Symmetric means the tree is a mirror of itself, not that two trees are identical. Compare left with right as mirrors.
Getting the mirror comparison wrong. The outer nodes are left.left vs right.right. The inner nodes are left.right vs right.left. This is different from same-tree comparison.
Not handling the base cases: both null (true), one null (false), values differ (false).
Forgetting that a single node tree is symmetric. Return true.
Trying to solve it by inverting one subtree and then comparing with same-tree. While technically correct, it's O(n) extra work. Direct mirror comparison (l.left vs r.right) is cleaner.
Solution Code
def isSymmetric(root):
def mirror(l, r):
if not l and not r:
return True
if not l or not r:
return False
return l.val == r.val and mirror(l.left, r.right) and mirror(l.right, r.left)
return mirror(root.left, root.right) if root else TrueFrequently Asked Questions
What is the Symmetric Tree problem?
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
How do you solve Symmetric Tree?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Symmetric Tree?
Symmetric Tree is asked at Google, Meta, Amazon, Microsoft, Apple. It is a easy difficulty problem.
What are common mistakes on Symmetric Tree?
- Confusing this with "same tree." Symmetric means the tree is a mirror of itself, not that two trees are identical. Compare left with right as mirrors.
- Getting the mirror comparison wrong. The outer nodes are left.left vs right.right. The inner nodes are left.right vs right.left. This is different from same-tree comparison.
- Not handling the base cases: both `null` (`true`), one `null` (`false`), values differ (`false`).
- Forgetting that a single node tree is symmetric. Return `true`.
- Trying to solve it by inverting one subtree and then comparing with same-tree. While technically correct, it's `O(n)` extra work. Direct mirror comparison (l.left vs r.right) is cleaner.