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.
Approach 1: Recursive Mirror Check (Depth-First Search) (Time: O(n), Space: O(h))
This approach compares the left and right subtrees using recursion. Two nodes are considered mirrors if their values are equal and their children are symmetric in opposite order: left.left matches right.right and left.right matches right.left. Start by calling a helper function with the root’s left and right children. The recursion continues until both nodes are null (symmetric) or a mismatch appears. Because every node is visited once, the time complexity is O(n). The recursion stack uses O(h) space where h is the tree height. This method is the most intuitive way to reason about symmetry in a binary tree and naturally fits depth-first search patterns.
Approach 2: Iterative Queue Comparison (Breadth-First Search) (Time: O(n), Space: O(n))
The iterative approach replaces recursion with a queue. Push the root’s left and right children as a pair. At each step, pop two nodes and compare them. If both are null, continue. If only one is null or their values differ, the tree is not symmetric. Otherwise, push their children in mirrored order: left.left with right.right, and left.right with right.left. The queue ensures nodes are processed level by level while maintaining mirror pairing. Each node enters the queue at most once, giving O(n) time and O(n) space in the worst case. This version mirrors the recursive logic but uses explicit state management, a common technique in breadth-first search problems.
Recommended for interviews: The recursive DFS solution is typically expected because the mirror relationship is easy to express with a helper function. It clearly demonstrates your understanding of recursion and tree structure. The iterative queue approach shows deeper control over traversal mechanics and avoids recursion stack limits. Mentioning both approaches during interviews signals strong mastery of tree traversal patterns.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Mirror Check (DFS) | O(n) | O(h) | Best for interviews and clean logic when recursion is acceptable |
| Iterative Queue Comparison (BFS) | O(n) | O(n) | Useful when avoiding recursion or when practicing explicit BFS traversal |
Symmetric Tree - Leetcode 101 - Python • NeetCodeIO • 48,743 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