Symmetric Tree

• Difficulty: Easy
• Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree
• Link: https://leetcode.com/problems/symmetric-tree/

Problem Description

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

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

Follow up: Could you solve it both recursively and iteratively?

Solution

1. Problem Deconstruction (500+ words)

Technical Reformulation: Given the root node of a binary tree, determine if the tree exhibits mirror symmetry about its vertical axis through the root. Formally, for every node in the left subtree, there must exist a corresponding node in the right subtree at the mirror position with identical value, and vice versa. The tree structure and values must satisfy the symmetric property recursively throughout all levels.

Beginner-Friendly Explanation: Imagine you could fold the tree exactly down the middle through the root node. If all nodes on the left side perfectly match their corresponding nodes on the right side when folded, the tree is symmetric. The left child’s left subtree should match the right child’s right subtree, and the left child’s right subtree should match the right child’s left subtree, with all values being equal at matching positions.

Mathematical Formalization: Let T be a binary tree with root node r. Define a mirror function M that checks symmetry:

• M(T₁, T₂) = true if both T₁ and T₂ are empty
• M(T₁, T₂) = false if one tree is empty and the other is not
• M(T₁, T₂) = (value(T₁) = value(T₂)) ∧ M(left(T₁), right(T₂)) ∧ M(right(T₁), left(T₂))

The tree is symmetric if M(left®, right®) = true.

Constraint Analysis:

• Node count range [1, 1000]: Eliminates empty tree case. Enables O(n²) solutions but O(n) preferred.
• Value range [-100, 100]: Values fit in single byte. No overflow concerns.
• Maximum depth ~1000: Recursive solutions need ~1KB stack space (acceptable).
• Implicit edge cases: Single node (always symmetric), unbalanced trees, negative values, duplicate values in asymmetric positions.

2. Intuition Scaffolding

Real-World Metaphor: Like checking if a Rorschach inkblot is perfectly symmetrical. Each ink splatter on the left must have an identical mirror-image splatter on the right.

Gaming Analogy: In a puzzle game with mirrored rooms, objects in the left room must be arranged as mirror images of objects in the right room. Checking each corridor recursively reveals if the entire level is symmetric.

Math Analogy: The tree forms a bipartite graph where we verify if the adjacency matrix is symmetric about the anti-diagonal when level-order traversal is considered.

Common Pitfalls:

1. Shallow Comparison: Only checking immediate children (fails on deeper asymmetry)
2. Value-Only Matching: Ensuring values match but ignoring structure
3. Level-Order Trap: Assuming symmetric level-order means tree symmetry
4. Single-Sided Traversal: Only traversing left subtree completely
5. Null Handling: Incorrectly handling cases where one subtree exists and other doesn’t

3. Approach Encyclopedia

Brute Force (Naive Serialization):

def isSymmetric_brute(root):
    def serialize_left_first(node):
        if not node: return "null"
        return (f"({node.val},{serialize_left_first(node.left)},"
                f"{serialize_left_first(node.right)})")
    
    def serialize_right_first(node):
        if not node: return "null"
        return (f"({node.val},{serialize_right_first(node.right)},"
                f"{serialize_right_first(node.left)})")
    
    if not root: return True
    left_serialized = serialize_left_first(root.left)
    right_serialized = serialize_right_first(root.right)
    return left_serialized == right_serialized

Complexity: Time O(n), Space O(n) - Each node visited once, but string concatenation adds overhead.

Recursive DFS (Optimal):

def isSymmetric_recursive(root):
    def mirror_match(left, right):
        # Both null - symmetric base case
        if not left and not right: return True
        # One null, one not - asymmetry
        if not left or not right: return False
        # Values must match and subtrees must be mirrors
        return (left.val == right.val and 
                mirror_match(left.left, right.right) and 
                mirror_match(left.right, right.left))
    
    return mirror_match(root.left, root.right) if root else True

Complexity Proof:

• Time: T(n) = 2T(n/2) + O(1) → O(n) by Master Theorem
• Space: O(h) where h = tree height, worst-case O(n) for skewed trees

Iterative BFS (Queue-Based):

from collections import deque

def isSymmetric_iterative(root):
    if not root: return True
    queue = deque([(root.left, root.right)])
    
    while queue:
        left, right = queue.popleft()
        if not left and not right: continue
        if not left or not right: return False
        if left.val != right.val: return False
        
        queue.append((left.left, right.right))
        queue.append((left.right, right.left))
    
    return True

Complexity Proof:

• Time: O(n) - Each node pair visited once
• Space: O(w) where w = maximum width, worst-case O(n) for complete trees

Visualization:

Initial: [ (2,2) ]
Level 1: Compare 2 vs 2 ✓
         Enqueue: (3,3), (4,4)
Queue: [ (3,3), (4,4) ]
Level 2: Compare 3 vs 3 ✓ → Enqueue: (null,null), (null,null)
         Compare 4 vs 4 ✓ → Enqueue: (null,null), (null,null)
All null pairs → Symmetric!

4. Code Deep Dive

Optimal Recursive Solution:

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def mirror_match(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
            # Base case: Both subtrees empty
            if not left and not right:
                return True
            # Structural asymmetry: One exists, other doesn't
            if not left or not right:
                return False
            # Value mismatch at current mirror positions
            if left.val != right.val:
                return False
            # Recursive mirror check: outer pairs and inner pairs
            return (mirror_match(left.left, right.right) and 
                    mirror_match(left.right, right.left))
        
        # Handle empty tree and start mirror comparison
        return mirror_match(root.left, root.right) if root else True

Line-by-Line Analysis:

• Line 3-4: Handle the null-symmetric base case first
• Line 6-7: Catch structural imbalance early (critical for Example 2)
• Line 9-10: Value comparison at current mirror positions
• Line 12-13: Recursively verify outer symmetry (left.left vs right.right) and inner symmetry (left.right vs right.left)

Edge Case Handling:

• Example 1: Perfect symmetry - all recursive calls return True
• Example 2: root = [1,2,2,null,3,null,3] fails at Line 6-7 when comparing (null,3)
• Single Node: root = [1] → Line 16 returns True (both children null)

5. Complexity War Room

Hardware-Aware Analysis:

• 1000 nodes × 4 bytes = ~4KB memory for recursion stack (fits in L1 cache)
• Pointer chasing has good cache locality for DFS traversal
• BFS approach uses more memory but better for very wide trees

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n)	O(n)	6/10	❌ Overly complex
Recursive DFS	O(n)	O(h)	9/10	✅ Preferred
Iterative BFS	O(n)	O(w)	8/10	✅ Good alternative
Iterative DFS	O(n)	O(h)	7/10	⚠️ Less intuitive

6. Pro Mode Extras

Algorithm Variants:

• Modified Tree: “Check if tree can be made symmetric with k value changes”
• k-Symmetric: “Verify symmetry up to k levels deep”
• Multi-way Trees: “Generalize to n-ary tree symmetry”

Follow-up Adaptations:

# If asked for iterative DFS
def isSymmetric_dfs(root):
    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: return False
        if left.val != right.val: return False
        
        stack.append((left.left, right.right))
        stack.append((left.right, right.left))
    
    return True

Interview Cheat Sheet:

• First Mention: “This is a tree symmetry problem requiring mirror comparison”
• Complexity First: “Optimal solution runs in O(n) time with O(h) space”
• Dual Approach: “I’ll present both recursive and iterative solutions”
• Edge Cases: “Single node, unbalanced trees, value vs structure mismatches”