Symmetric Tree
The key idea
A tree mirrors itself exactly when, for every mirrored pair of nodes, their values match and the outer children (left.left vs right.right) and inner children (left.right vs right.left) also mirror. Compare the tree with itself one mirrored pair at a time.
Problem
Given the root of a binary tree, check whether it is a *mirror* of itself (that is, symmetric around its center).
A tree is symmetric when its left subtree is the mirror image of its right subtree. Concretely, the two subtrees must hold the same values at mirrored positions: the left child of one node lines up with the right child of its counterpart, and the right child lines up with the counterpart's left child. Return true if the tree is symmetric and false otherwise.
Constraints
- The number of nodes in the tree is in the range
[1, 1000]. -100 <= Node.val <= 100
Examples
Input: root = [1,2,2,3,4,4,3]
Output: true
Input: root = [1,2,2,null,3,null,3]
Output: false
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY