DSA problem
Symmetric Tree
Given the root of a binary tree, return true if the tree is a mirror of itself — that is, the left subtree is the mirror image of the right subtree. Symmetric trees read the same when reflected across the vertical axis through the root.
The key insight is that symmetry is not a property of a single subtree; it is a property of a pair of subtrees. A single tree is symmetric iff its left and right children form a mirrored pair. Define a helper isMirror(a, b) that decides whether two subtrees are mirrors of each other. The recurrence is: both null → mirror; exactly one null → not mirror; a.val == b.val and isMirror(a.left, b.right) and isMirror(a.right, b.left). Notice the cross-pairing: a's left is compared to b's right, and vice versa.
The recursion is preorder by construction — we test the pair of roots before walking down. The traversal visits every node exactly once, so the time complexity is O(n). The space complexity is O(h) for the recursion stack, where h is the height of the tree.
An iterative version uses a queue or stack of node pairs. Push (root.left, root.right); in a loop pop a pair, do the same null/value checks, then push (a.left, b.right) and (a.right, b.left). The iterative form is useful when you want to avoid deep recursion on heavily skewed inputs.
Examples
root = [1,2,2,3,4,4,3]trueroot = [1,2,2,null,3,null,3]falseroot = [1]trueConstraints
- The number of nodes in the tree is in the range [1, 1000].
- -100 <= Node.val <= 100
- Follow-up: solve it both recursively and iteratively.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.