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 <= 100The goal of #101 Symmetric Tree is to determine whether a binary tree is a mirror of itself. A tree is symmetric if the left subtree is a mirror reflection of the right subtree. Instead of comparing nodes within the same subtree, the key idea is to compare nodes across subtrees.
A common strategy uses Depth-First Search (DFS). You recursively compare two nodes: one from the left subtree and one from the right subtree. For the tree to remain symmetric, their values must match and their children must be mirrors as well (i.e., left.left with right.right, and left.right with right.left).
An alternative method uses Breadth-First Search (BFS) with a queue to iteratively compare node pairs level by level. This approach simulates the mirror comparison without recursion.
Both approaches visit each node once, leading to efficient performance. Choosing between DFS and BFS typically depends on whether you prefer a recursive or iterative traversal pattern.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS (Recursive Mirror Check) | O(n) | O(h) recursion stack |
| BFS (Queue-Based Comparison) | O(n) | O(n) |
NeetCodeIO
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.
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.
1#include <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 bool isMirror(TreeNode* t1, TreeNode* t2) {
14 if (!t1 && !t2) return true;
if (!t1 || !t2) return false;
return (t1->val == t2->val) &&
isMirror(t1->right, t2->left) &&
isMirror(t1->left, t2->right);
}
bool isSymmetric(TreeNode* root) {
return isMirror(root, root);
}
};This C++ solution uses a class Solution with a method isMirror to recursively check if two subtrees are mirror images. The isSymmetric method starts this check with the tree's root node.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Symmetric Tree is a common interview question at many top tech companies. It tests understanding of binary tree traversal, recursion, and how to compare structural properties of trees.
Yes, the problem can be solved iteratively using a queue. In this approach, node pairs are pushed into the queue and compared level by level to ensure the tree maintains mirror symmetry.
The optimal approach is to compare the left and right subtrees as mirror images. This can be done using recursion (DFS) or an iterative BFS with a queue. Both methods check corresponding nodes across the two subtrees and run in O(n) time.
For a recursive solution, the call stack naturally handles traversal. For an iterative approach, a queue is typically used to store pairs of nodes that should mirror each other during BFS traversal.
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.