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.
This approach uses recursion to compare the left subtree and right subtree of the binary tree. For two trees to be mirror images, the following three conditions must be true:
Recursion is an elegant way to check this condition for each node in the tree.
This C code defines a recursive function isMirror that checks if two trees are mirror images. The isSymmetric function calls isMirror with the root node passed twice. The function checks if both nodes are null (returns true if so) or if one is null (returns false). It then checks if the values are the same and recursively calls isMirror on the opposite children nodes.
Time Complexity: O(n), where n is the number of nodes in the binary tree, since we traverse every node once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion call stack.
This approach utilizes a queue data structure to iteratively compare nodes in the binary tree. It behaves like the recursive method mirroring trees, but it exchanges recursion for a loop that dequeues two nodes at a time.
This C solution employs a queue data structure for comparing values of nodes iteratively. A newly defined data structure and its pertinent functions encapsulate the queue. The code mimics the recursive solution’s pattern: null-checking nodes, confirming equality of values, and inserting children appropriately for subsequent comparisons.
Time Complexity: O(n), n being indicative of the number of nodes enumerated.
Space Complexity: O(n), underscored by the queue's need for storing nodes in tandem with iteration.
We design a function dfs(root1, root2) to determine whether two binary trees are symmetric. The answer is dfs(root.left, root.right).
The logic of the function dfs(root1, root2) is as follows:
root1 and root2 are null, the two binary trees are symmetric, and we return true;root1 and root2 is null, or root1.val neq root2.val, we return false;root1 is symmetric with the right subtree of root2, and whether the right subtree of root1 is symmetric with the left subtree of root2, using recursion.The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n), where n is the number of nodes in the binary tree, since we traverse every node once. |
| Iterative Approach | Time Complexity: O(n), n being indicative of the number of nodes enumerated. |
| Recursion | — |
| 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 |
Symmetric Tree - Leetcode 101 - Python • NeetCodeIO • 63,757 views views
Watch 9 more video solutions →Practice Symmetric Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor