12. Symmetric Tree
easyAsked at DatabricksDetermine if a binary tree is a mirror of itself around its center. Databricks asks this to test paired recursion — comparing two pointers that walk in opposite directions, which is the same primitive used in plan-folding and palindrome detection.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Databricks loops.
- LeetCode Discuss (2025-10)— Databricks coding warm-up; tests paired-recursion fluency.
- Glassdoor (2026-Q1)— Used as a 10-minute phone-screen problem before harder tree questions.
Problem
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Constraints
The number of nodes in the tree is in the range [1, 1000].-100 <= Node.val <= 100
Examples
Example 1
root = [1,2,2,3,4,4,3]trueExample 2
root = [1,2,2,null,3,null,3]falseApproaches
1. Inorder serialize and check palindrome
Walk inorder, check if the sequence is a palindrome.
- Time
- O(n)
- Space
- O(n)
function isSymmetric(root) {
const arr = [];
function walk(n) { if (!n) { arr.push(null); return; } walk(n.left); arr.push(n.val); walk(n.right); }
walk(root);
for (let i = 0, j = arr.length - 1; i < j; i++, j--) if (arr[i] !== arr[j]) return false;
return true;
}Tradeoff: Wrong intuition. Inorder sequences alone don't capture structure — two non-symmetric trees can have the same inorder.
2. Mirror recursion with two pointers
Walk one pointer left-first, the other right-first; require val match and mirrored descent.
- Time
- O(n)
- Space
- O(h) recursion stack
function isSymmetric(root) {
function mirror(a, b) {
if (!a && !b) return true;
if (!a || !b) return false;
return a.val === b.val
&& mirror(a.left, b.right)
&& mirror(a.right, b.left);
}
return !root || mirror(root.left, root.right);
}Tradeoff: Single pass, exact. The trick is the crossed recursion: a.left vs b.right and a.right vs b.left.
Databricks-specific tips
Databricks grades the paired-recursion pattern because it's the same shape Catalyst uses for plan rewriting (e.g., folding two equivalent branches). The bonus signal is volunteering the iterative version with a queue holding pairs of nodes — useful when JVM stack depth is a concern. Don't fall into the inorder-palindrome trap; if you mention it, immediately call out why it's wrong.
Common mistakes
- Recursing same-side (a.left vs b.left) — that compares for equality, not mirror.
- Skipping the (!a || !b) base case — null dereference on lopsided trees.
- Using BFS without pairing nodes — you must enqueue PAIRS, not individual nodes.
Follow-up questions
An interviewer at Databricks may pivot to one of these next:
- Iterative version using a queue of (left, right) pairs.
- Determine the longest symmetric subtree.
- Plan-folding: detect when two query subtrees are mirror equivalents (e.g., commutative join).
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why crossed recursion?
Symmetry means a's left mirrors b's right. Recursing same-side would test equality, not mirroring.
Can BFS work?
Yes — enqueue (root.left, root.right) and on each pop, compare the pair and enqueue (left.left, right.right) and (left.right, right.left).