Problem Statement:
Given the root of a binary tree, check whether it is a mirror of itself(i.e., symmetric around its center).
Examples:
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:
- The number of nodes in the tree is in the range
[1, 1000]. -100 <= Node.val <= 100
Approach: Bottom Up
- Use a helper function
isMirror(left, right)to compare two nodes. - The tree is symmetric if:
- Both left and right subtrees are
null→ returntrue. - Only one is
null→ returnfalse. - Their values match and:
- Left’s left subtree mirrors Right’s right subtree.
- Left’s right subtree mirrors Right’s left subtree.
- Both left and right subtrees are
- Start the comparison with
root.leftandroot.right.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: root = [1, 2, 3, null, 4]
Tree Structure:
1
/ \
2 3
\
4
Function call: isSymmetric(root)
→ Calls isMirror(root.left, root.right)
→ isMirror(2, 3)
- Both are not null → OK
- Compare values: 2 === 3 → false
→ Return false
Function returns false (not symmetric)
Output: Result: false
var isSymmetric = function(root) {
let isMirror = (left, right) => {
if(!left && !right) return true;
if(!left || !right) return false;
return left.val === right.val &&
isMirror(left.left, right.right) &&
isMirror(left.right, right.left);
}
return isMirror(root.left, root.right);
};
def isMirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
isMirror(left.left, right.right) and
isMirror(left.right, right.left))
def isSymmetric(root):
return isMirror(root.left, root.right)
public boolean isMirror(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
return (left.val == right.val) &&
isMirror(left.left, right.right) &&
isMirror(left.right, right.left);
}
public boolean isSymmetric(TreeNode root) {
return isMirror(root.left, root.right);
}
bool isMirror(TreeNode* left, TreeNode* right) {
if (!left && !right) return true;
if (!left || !right) return false;
return (left->val == right->val) &&
isMirror(left->left, right->right) &&
isMirror(left->right, right->left);
}
bool isSymmetric(TreeNode* root) {
return isMirror(root->left, root->right);
}
bool isMirror(struct TreeNode* left, struct TreeNode* right) {
if (!left && !right) return true;
if (!left || !right) return false;
return (left->val == right->val) &&
isMirror(left->left, right->right) &&
isMirror(left->right, right->left);
}
bool isSymmetric(struct TreeNode* root) {
return isMirror(root->left, root->right);
}
public bool IsMirror(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
return left.val == right.val &&
IsMirror(left.left, right.right) &&
IsMirror(left.right, right.left);
}
public bool IsSymmetric(TreeNode root) {
return IsMirror(root.left, root.right);
}
