🎨Now live: Try our Free AI Image Generation Feature

Intuition
A tree is symmetric if the left subtree is a mirror reflection of the right subtree. This means that for every node in the left subtree, there should be a corresponding node in the right subtree with the same value, and their children should also be mirror reflections of each other.
Approach
- Base Case:
- If the root is
None
, the tree is symmetric by definition. - Recursive Helper Function:
- The helper function checks if two subtrees are mirrors of each other.
- Base Cases:
- If both nodes are
None
, they are symmetric. - If only one of the nodes isNone
, they are not symmetric. - If the values of the two nodes are different, they are not symmetric. - Recursive Case: - Recursively check if the left subtree of the first node is a mirror of the right subtree of the second node and the right subtree of the first node is a mirror of the left subtree of the second node.
Complexity
Time Complexity:
O(N), where N is the number of nodes in the binary tree. Each node is visited once.
Space Complexity:
O(H), where H is the height of the tree. This is due to the space required for the recursion stack. In the worst case (for a completely unbalanced tree), the height is N, and in the best case (for a completely balanced tree), the height is log(N).
Code
C++
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return helper(root->left, root->right);
}
private:
bool helper(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr && root2 == nullptr) return true;
if (root1 == nullptr || root2 == nullptr) return false;
if (root1->val != root2->val) return false;
return helper(root1->left, root2->right) && helper(root1->right, root2->left);
}
};
Python
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
return self.helper(root.left, root.right)
def helper(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if root1 is None and root2 is None:
return True
if root1 is None or root2 is None:
return False
if root1.val != root2.val:
return False
return self.helper(root1.left, root2.right) and self.helper(root1.right, root2.left)
Java
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return helper(root.left, root.right);
}
private boolean helper(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null) return false;
if (root1.val != root2.val) return false;
return helper(root1.left, root2.right) && helper(root1.right, root2.left);
}
}
JavaScript
var isSymmetric = function (root)
{
if (!root) return true;
function helper(root1, root2)
{
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null) return false;
if (root1.val !== root2.val) return false;
return helper(root1.left, root2.right) && helper(root1.right, root2.left);
}
return helper(root.left, root.right);
};