101. Symmetric Tree - Explanation

Problem Link

1. Depth First Search

Intuition

A tree is symmetric if its left subtree is a mirror reflection of its right subtree. Two trees are mirrors of each other if their roots have the same value, and the left subtree of one is a mirror of the right subtree of the other (and vice versa). We can check this recursively by comparing pairs of nodes that should be mirror images of each other.

Algorithm

1. Define a recursive helper that takes two nodes: one from the left subtree and one from the right subtree.
2. If both nodes are null, they are mirrors (return true).
3. If only one is null, or their values differ, they are not mirrors (return false).
4. Recursively check:
   • The left child of the left node against the right child of the right node.
   • The right child of the left node against the left child of the right node.
5. Return true only if both recursive checks pass.
6. Start by comparing the root's left and right children.

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

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ for recursion stack.

---

2. Iterative DFS

Intuition

The recursive solution can be converted to an iterative one using a stack. Instead of implicit recursive calls, we explicitly push pairs of nodes onto a stack. Each pair represents two nodes that should be mirror images. By processing pairs from the stack, we maintain the same comparison logic without recursion.

Algorithm

1. Push the initial pair (root.left, root.right) onto the stack.
2. While the stack is not empty:
   • Pop a pair of nodes.
   • If both are null, continue to the next pair.
   • If only one is null or their values differ, return false.
   • Push two new pairs: (left.left, right.right) and (left.right, right.left).
3. If all pairs pass, return true.

# 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

        stack = [(root.left, root.right)]
        while stack:
            left, right = stack.pop()
            if not left and not right:
                continue
            if not left or not right or left.val != right.val:
                return False
            stack.append((left.left, right.right))
            stack.append((left.right, right.left))
        return True

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Breadth First Search

Intuition

BFS processes nodes level by level using a queue. For symmetry checking, we enqueue pairs of nodes that should be mirrors. Processing the queue ensures we compare nodes at the same depth before moving deeper. This approach gives a level-by-level validation of the mirror property.

Algorithm

1. Initialize a queue with the pair (root.left, root.right).
2. While the queue is not empty:
   • For each pair in the current level:
     • Dequeue a pair.
     • If both are null, continue.
     • If only one is null or values differ, return false.
     • Enqueue pairs: (left.left, right.right) and (left.right, right.left).
3. If all comparisons pass, return true.

# 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

        queue = deque([(root.left, root.right)])
        while queue:
            for _ in range(len(queue)):
                left, right = queue.popleft()
                if not left and not right:
                    continue
                if not left or not right or left.val != right.val:
                    return False
                queue.append((left.left, right.right))
                queue.append((left.right, right.left))

        return True

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

Common Pitfalls

Comparing Wrong Node Pairs

A frequent mistake is comparing left.left with right.left instead of left.left with right.right. For a mirror reflection, the left child of the left subtree must match the right child of the right subtree, and vice versa.

Forgetting to Handle Null Cases First

When checking symmetry, you must handle the null cases before accessing node values. Checking left.val == right.val when either node is null will cause a null pointer exception. Always check if both are null (return true) or only one is null (return false) before comparing values.