Watch 10 video solutions for Symmetric Tree, a easy level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by NeetCodeIO has 63,757 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Input: root = [1,2,2,3,4,4,3] Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3] Output: false
Constraints:
[1, 1000].-100 <= Node.val <= 100Follow up: Could you solve it both recursively and iteratively?
Problem Overview: Given the root of a binary tree, determine whether the tree is symmetric around its center. A tree is symmetric if the left subtree is a mirror reflection of the right subtree — every node on the left must match the corresponding node on the right in value and position.
This problem is fundamentally about comparing two subtrees for mirror equality. Instead of checking a subtree against itself, you compare the left child of one subtree with the right child of the other. The pattern naturally fits recursive tree traversal or an iterative queue-based comparison.
Approach 1: Recursive Mirror Check (DFS) (Time: O(n), Space: O(h))
The recursive solution directly models the mirror definition. You write a helper function that compares two nodes. If both nodes are null, the structure matches. If only one is null or the values differ, the tree is not symmetric. Otherwise, recursively compare left.left with right.right and left.right with right.left.
This traversal touches each node exactly once, giving O(n) time complexity. The recursion depth equals the tree height, so space complexity is O(h) due to the call stack. This approach is clean and closely follows the mirror definition of symmetry, making it easy to reason about in interviews. It relies on concepts from Depth-First Search and Binary Tree recursion patterns.
Approach 2: Iterative Mirror Check (BFS with Queue) (Time: O(n), Space: O(n))
The iterative approach simulates the mirror comparison using a queue. Start by pushing the root's left and right children. While the queue is not empty, pop two nodes at a time. If both are null, continue. If only one is null or their values differ, the tree is not symmetric.
If the values match, enqueue their children in mirror order: (left.left, right.right) and (left.right, right.left). This ensures that nodes that should mirror each other are always compared together. Every node is processed once, resulting in O(n) time complexity. The queue may hold up to a full tree level, so the worst‑case space complexity is O(n). This approach mirrors a level-order traversal using Breadth-First Search.
Recommended for interviews: The recursive DFS solution is the most common answer because it directly encodes the mirror definition and requires minimal code. Interviewers often expect this approach first. The iterative queue solution is equally efficient and demonstrates that you understand both DFS and BFS traversal patterns in a Tree. Mentioning both approaches shows deeper understanding of traversal strategies.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Mirror Check (DFS) | O(n) | O(h) | Best for interviews and clean implementations when recursion depth is manageable |
| Iterative Mirror Check (BFS Queue) | O(n) | O(n) | Useful when avoiding recursion or when implementing level-order style traversal |