Symmetric Tree — Mirror Recursion

Sanjeev SharmaSanjeev Sharma
1 min read

Advertisement

Problem 349 · Symmetric Tree

Difficulty: Easy · Pattern: Mirror DFS

Solutions

# Python
def isSymmetric(root):
    def mirror(left, right):
        if not left and not right: return True
        if not left or not right: return False
        return (left.val == right.val and
                mirror(left.left, right.right) and
                mirror(left.right, right.left))
    return mirror(root.left, root.right) if root else True
// Java
public boolean isSymmetric(TreeNode root) {
    return root == null || mirror(root.left, root.right);
}
boolean mirror(TreeNode l, TreeNode r) {
    if (l==null&&r==null) return true;
    if (l==null||r==null) return false;
    return l.val==r.val && mirror(l.left,r.right) && mirror(l.right,r.left);
}
// C++
bool mirror(TreeNode* l, TreeNode* r) {
    if (!l && !r) return true;
    if (!l || !r) return false;
    return l->val==r->val && mirror(l->left,r->right) && mirror(l->right,r->left);
}
bool isSymmetric(TreeNode* root) { return !root || mirror(root->left, root->right); }

Complexity

  • Time: O(n)
  • Space: O(h)

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro