#101 Symmetric Tree
frequently reported atLinkedInBloombergMicrosoftAmazonGoogleMeta
the problem
In plain words
Check whether a binary tree is the mirror image of itself: fold it down the middle and the left half must land exactly on the right half, values included. Return true or false.
in root = [1,2,2,3,4,4,3]
out true
The left half 2 → (3, 4) mirrors the right half 2 → (4, 3).
in root = [1,2,2,null,3,null,3]
out false
Both 3s hang on the right side of their parents, so the halves don't mirror.
- 1 ≤ number of nodes ≤ 1000
- -100 ≤ Node.val ≤ 100
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTree DFS (bottom-up)
It's Same Tree with crossed wires. Compare root.left with root.right, then always pair an outside child with an outside child (a.left, b.right) and an inside child with an inside child (a.right, b.left).
solutions
From brute force to optimal
Build a mirrored copy of the whole tree, then check with Same Tree that it equals the original.
- mirror(node) = a new node with mirror(right) on the left and mirror(left) on the right.
- Return same(root, mirror(root)).
One pass to build the copy, one pass to compare.
The copy holds n new nodes, plus the O(h) recursion stack.
class Solution { public boolean isSymmetric(TreeNode root) { return same(root, mirror(root)); // symmetric = equal to its own mirror image } /** A brand-new tree that is the mirror image of node's subtree (the input is not touched). */ private TreeNode mirror(TreeNode node) { if (node == null) return null; return new TreeNode(node.val, mirror(node.right), mirror(node.left)); } private boolean same(TreeNode a, TreeNode b) { if (a == null || b == null) return a == b; return a.val == b.val && same(a.left, b.left) && same(a.right, b.right); }}isMirror(a, b): a and b are mirror images if their values match, a.left mirrors b.right, and a.right mirrors b.left.
- Start with isMirror(root.left, root.right).
- Both null → true. One null → false. Values differ → false.
- Return isMirror(a.left, b.right) && isMirror(a.right, b.left).
Every node is compared once with its mirror partner, and && stops at the first mismatch.
Recursion depth = height: O(log n) when balanced, O(n) for a deep V shape.
class Solution { public boolean isSymmetric(TreeNode root) { return root == null || isMirror(root.left, root.right); } /** True if subtree a is the mirror image of subtree b. */ private boolean isMirror(TreeNode a, TreeNode b) { if (a == null && b == null) return true; // both spots empty: a match if (a == null || b == null) return false; // only one side has a node if (a.val != b.val) return false; return isMirror(a.left, b.right) // the outside pair && isMirror(a.right, b.left); // the inside pair }}Dry run
The same three checks, but the pairs wait in an ArrayDeque instead of on the call stack.
- Offer (root.left, root.right).
- Poll a pair and run the checks.
- Offer (a.left, b.right) and (a.right, b.left).
Each pair is polled once.
The queue holds about one level of pairs — and no recursion, so no stack-depth risk.
class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) return true; Deque<TreeNode[]> pairs = new ArrayDeque<>(); // a pair may hold nulls; the deque never does pairs.offer(new TreeNode[] {root.left, root.right}); while (!pairs.isEmpty()) { TreeNode[] pair = pairs.poll(); TreeNode a = pair[0], b = pair[1]; if (a == null && b == null) continue; if (a == null || b == null || a.val != b.val) return false; pairs.offer(new TreeNode[] {a.left, b.right}); // the outside pair pairs.offer(new TreeNode[] {a.right, b.left}); // the inside pair } return true; }}in the room
How to say it in the interview
talk track
- Say the reduction first: "a tree is symmetric when its left subtree is the mirror of its right subtree."
- Write isMirror(a, b) with Same Tree's three checks, then the crossed recursion.
- LeetCode's own follow-up asks for both versions: offer the queue-of-pairs one for very deep trees.
traps
- Recursing on (a.left, b.left) and (a.right, b.right) — that is Same Tree, not a mirror.
- Checking that each level's values read the same both ways while skipping nulls: [1,2,2,null,3,null,3] has levels [1], [2,2], [3,3] — all palindromes — yet it is not symmetric. Keep the nulls, or compare pairs.
- Calling isMirror(root, root) works, but compares every pair twice.
what they ask next
Follow-ups
Can you do it without recursion?
Yes: a queue (or stack) of node pairs. Offer (a.left, b.right) and (a.right, b.left); a pair of two nulls is simply skipped. That's the third approach above.
How is this related to Invert Binary Tree?
A tree is symmetric exactly when its left subtree equals the inverted right subtree — which is what the brute force checks with a mirrored copy.
before you submit
Edge cases to test
- One node → true.
- Equal values in the wrong shape: [1,2,2,null,3,null,3] → false.
- A deep V (two long arms): the recursion goes as deep as one arm is long.
practise next
Similar problems
- #100Same TreeEasyin Tree Recursion
- #226Invert Binary TreeEasyin Tree Recursion
- #572Subtree of Another TreeEasyin Tree Recursion