Symmetric Tree

XXX. Symmetric Tree

Tree

DFS

Iterative

Problem Statement:

Given the root of a binary tree, determine if it is a mirror of itself (i.e., symmetric around its center).

Algorithm:

Recursive Solution:

1. Check if the root is null. If yes, return true.
2. Use a helper function isMirror to recursively compare the left and right subtrees.
3. In isMirror:
   • If both nodes are null, return true.
   • If one node is null or their values don't match, return false.
   • Otherwise, check:
     • Left subtree of the first node with the right subtree of the second node.
     • Right subtree of the first node with the left subtree of the second node.

Iterative Solution:

1. If the root is null, return true.
2. Use a stack to perform iterative comparison:
   • Push the left and right children of the root onto the stack.
   • While the stack is not empty:
     • Pop two nodes from the stack.
     • If both nodes are null, continue.
     • If one is null or their values don't match, return false.
     • Push the left and right children of these nodes in mirrored order.

Complexity:

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(h), where h is the height of the tree (for recursion stack or iterative stack).

Java Implementation:

// Recursive solution
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    return (p.val == q.val) 
        && isMirror(p.left, q.right) 
        && isMirror(p.right, q.left);
}

// Iterative solution with a stack
public boolean isSymmetricIterative(TreeNode root) {
    if (root == null) return true;
    Stack stack = new Stack<>();
    stack.push(root.left);
    stack.push(root.right);
    while (!stack.isEmpty()) {
        TreeNode n1 = stack.pop(), n2 = stack.pop();
        if (n1 == null && n2 == null) continue;
        if (n1 == null || n2 == null || n1.val != n2.val) return false;
        stack.push(n1.left);
        stack.push(n2.right);
        stack.push(n1.right);
        stack.push(n2.left);
    }
    return true;
}
                

Python Implementation:

# Recursive solution
def isSymmetric(root):
    if not root:
        return True
    return isMirror(root.left, root.right)

def isMirror(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    return (p.val == q.val 
            and isMirror(p.left, q.right) 
            and isMirror(p.right, q.left))

# Iterative solution with a stack
def isSymmetricIterative(root):
    if not root:
        return True
    stack = [root.left, root.right]
    while stack:
        n1, n2 = stack.pop(), stack.pop()
        if not n1 and not n2:
            continue
        if not n1 or not n2 or n1.val != n2.val:
            return False
        stack.extend([n1.left, n2.right, n1.right, n2.left])
    return True
                

C++ Implementation:

// Recursive solution
bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    return isMirror(root->left, root->right);
}

bool isMirror(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return (p->val == q->val 
            && isMirror(p->left, q->right) 
            && isMirror(p->right, q->left));
}

// Iterative solution with a stack
bool isSymmetricIterative(TreeNode* root) {
    if (!root) return true;
    stack stack;
    stack.push(root->left);
    stack.push(root->right);
    while (!stack.empty()) {
        TreeNode* n1 = stack.top(); stack.pop();
        TreeNode* n2 = stack.top(); stack.pop();
        if (!n1 && !n2) continue;
        if (!n1 || !n2 || n1->val != n2->val) return false;
        stack.push(n1->left);
        stack.push(n2->right);
        stack.push(n1->right);
        stack.push(n2->left);
    }
    return true;
}