101. Symmetric Tree

Problem Description

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

Solution: Recursive Approach

The most efficient and elegant solution to this problem involves a recursive approach. We define a helper function dfs that compares two subtrees to check if they are symmetric.

Algorithm:

1. Base Cases:

   • If both root1 and root2 are null, it implies both subtrees are empty, hence symmetric. Return true.
   • If only one of root1 or root2 is null, or their values (root1.val and root2.val) are different, the subtrees are not symmetric. Return false.

2. Recursive Step: If the base cases are not met, recursively check if:

   • The left subtree of root1 is symmetric to the right subtree of root2.
   • The right subtree of root1 is symmetric to the left subtree of root2.

   Return true only if both recursive calls return true; otherwise, return false.

3. Main Function: Call the dfs function with the left and right subtrees of the root node. This effectively compares the left and right halves of the tree for symmetry.

Code (Python):

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: TreeNode) -> bool:
        def dfs(root1: TreeNode, root2: TreeNode) -> bool:
            if not root1 and not root2:
                return True
            if not root1 or not root2 or root1.val != root2.val:
                return False
            return dfs(root1.left, root2.right) and dfs(root1.right, root2.left)
        return dfs(root.left, root.right)

Code (Java):

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
 
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return dfs(root.left, root.right);
    }
 
    private boolean dfs(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null || root1.val != root2.val) return false;
        return dfs(root1.left, root2.right) && dfs(root1.right, root2.left);
    }
}

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited at most once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be N. In the best case (a balanced tree), H would be log₂N.