Problem Description

You are given the root of a binary tree. Your task is to determine whether this tree is symmetric - meaning it forms a mirror image when folded along its center vertical axis.

A binary tree is considered symmetric if:

• The left and right subtrees are mirror images of each other
• For any two corresponding nodes in the left and right subtrees:
  • They have the same value
  • The left child of one node corresponds to the right child of the other node
  • The right child of one node corresponds to the left child of the other node

For example, a tree like this would be symmetric:

       1
      / \
     2   2
    / \ / \
   3  4 4  3

The solution uses a recursive helper function dfs(root1, root2) that compares two nodes to check if they are mirrors of each other:

1. If both nodes are None (represented by root1 == root2 when both are None), they are symmetric
2. If only one is None or their values differ, they are not symmetric
3. Otherwise, recursively check that:
   • The left child of root1 mirrors the right child of root2
   • The right child of root1 mirrors the left child of root2

The main function starts the comparison by calling dfs(root.left, root.right) to check if the left and right subtrees of the root are mirror images of each other.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While not a traditional graph problem, a binary tree is a special type of graph (specifically, a connected acyclic graph). Trees are a subset of graphs where each node has at most one parent.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure, where we need to check if the tree is symmetric around its center.

DFS

• Yes: We arrive at DFS (Depth-First Search) as our algorithm choice.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this symmetric tree problem.

This makes sense because:

• We need to traverse the tree structure to compare corresponding nodes
• DFS allows us to recursively explore each subtree and compare the left and right branches
• The recursive nature of DFS perfectly matches the recursive structure of checking symmetry (comparing left.left with right.right and left.right with right.left)
• We need to go deep into the tree structure to verify that all corresponding nodes match, which is exactly what DFS provides

The solution implements DFS through the recursive dfs helper function that explores both subtrees simultaneously, checking if they mirror each other at each level of recursion.

Intuition

To check if a tree is symmetric, imagine folding the tree along its center vertical axis like folding a piece of paper. If the tree is symmetric, the left and right halves should perfectly overlap.

The key insight is that for a tree to be symmetric, every node on the left side must have a corresponding "mirror" node on the right side. These mirror nodes must:

1. Have the same value
2. Be at the same level and mirrored position

Think about what makes two subtrees mirror images of each other. If we're comparing a left subtree and a right subtree:

• The root values must be equal
• The left child of the left subtree should mirror the right child of the right subtree
• The right child of the left subtree should mirror the left child of the right subtree

This naturally leads to a recursive approach where we compare pairs of nodes. Starting from the root's left and right children, we check if they're mirrors of each other by:

• Comparing their values
• Recursively checking if their children are properly mirrored

The beauty of this approach is that we're essentially traversing two trees simultaneously - one from the left side and one from the right side - and at each step verifying they're mirror images. If at any point we find nodes that should be mirrors but aren't (different values or one exists while the other doesn't), we know the tree isn't symmetric.

The base case occurs when we reach None nodes - two None nodes are considered symmetric since they represent the same "empty" structure on both sides.

Solution Approach

The solution implements a recursive DFS approach using a helper function dfs(root1, root2) to determine whether two binary trees are symmetric.

Implementation Details:

The main function isSymmetric initiates the comparison by calling dfs(root.left, root.right), checking if the left and right subtrees of the root are mirror images.

The dfs function follows this logic:

1. Base Case - Both nodes are null:

   • When root1 == root2 (both are None), the trees are symmetric at this point, return True
   • This handles the leaf nodes and empty subtrees

2. Asymmetric Cases:

   • If only one of root1 or root2 is None, the structure is different, return False
   • If both nodes exist but root1.val != root2.val, the values don't match, return False

3. Recursive Case:

   • Check if the left subtree of root1 mirrors the right subtree of root2: dfs(root1.left, root2.right)
   • Check if the right subtree of root1 mirrors the left subtree of root2: dfs(root1.right, root2.left)
   • Both conditions must be true for the trees to be symmetric, so we use and to combine them

Why This Works:

The algorithm effectively performs two synchronized DFS traversals:

• One traversal goes left-then-right on the left subtree
• The other goes right-then-left on the right subtree

At each step, we verify that the corresponding nodes have equal values. The recursive calls ensure we check all levels of the tree, from root to leaves.

Time Complexity: O(n) where n is the number of nodes, as we visit each node once Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack

Example Walkthrough

Let's walk through a small example to illustrate how the solution works:

       1
      / \
     2   2
    / \   \
   3   4   3

We want to check if this tree is symmetric. Let's trace through the recursive calls:

Step 1: Start with isSymmetric(root) where root has value 1

• Call dfs(root.left, root.right) → dfs(node_2_left, node_2_right)

Step 2: Compare the two nodes with value 2

• Both nodes exist and have value 2 ✓
• Now check if their children are mirrors:
  • Call dfs(node_2_left.left, node_2_right.right) → dfs(node_3, node_3)
  • Call dfs(node_2_left.right, node_2_right.left) → dfs(node_4, None)

Step 3: First recursive call: dfs(node_3, node_3)

• Both nodes exist and have value 3 ✓
• Check their children:
  • Call dfs(None, None) for left-right pair → returns True
  • Call dfs(None, None) for right-left pair → returns True
• Both are true, so this returns True

Step 4: Second recursive call: dfs(node_4, None)

• One node exists (value 4) but the other is None
• This is asymmetric, so returns False

Step 5: Back in Step 2

• First recursive call returned True
• Second recursive call returned False
• Since True and False = False, the entire check returns False

The tree is not symmetric because node 4 on the left doesn't have a corresponding mirror node on the right.

For contrast, if the tree were:

       1
      / \
     2   2
    / \ / \
   3  4 4  3

The same process would find that:

• Nodes with value 2 match ✓
• Left child 3 matches right child 3 ✓
• Right child 4 matches left child 4 ✓
• All recursive calls return True, so the tree is symmetric

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the binary tree.

The algorithm performs a depth-first search (DFS) traversal to check if the tree is symmetric. In the worst case, we need to visit every node in the tree exactly once. Each node is processed with O(1) operations (comparing values and making recursive calls). Therefore, the total time complexity is O(n).

Space Complexity: O(n) in the worst case, where n is the number of nodes in the binary tree.

The space complexity is determined by the recursive call stack. In the worst case, the tree could be completely unbalanced (e.g., a skewed tree forming a linked list), resulting in a recursion depth of O(n). In the best case of a perfectly balanced tree, the recursion depth would be O(log n), but we consider the worst-case scenario for complexity analysis. Therefore, the space complexity is O(n).

Common Pitfalls

1. Incorrect Mirror Comparison Direction

A frequent mistake is comparing the wrong pairs of nodes when checking for symmetry. Developers often incorrectly compare:

• left_node.left with right_node.left (same side comparison)
• left_node.right with right_node.right (same side comparison)

Incorrect Implementation:

# WRONG - This checks if subtrees are identical, not mirrors
return (is_mirror(left_node.left, right_node.left) and 
        is_mirror(left_node.right, right_node.right))

Correct Implementation:

# CORRECT - Cross comparison for mirror symmetry
return (is_mirror(left_node.left, right_node.right) and 
        is_mirror(left_node.right, right_node.left))

2. Forgetting to Handle the Root Node Properly

Some implementations mistakenly start the comparison from the root itself rather than its children:

Incorrect Implementation:

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    # WRONG - Comparing root with itself always returns True
    return is_mirror(root, root)

Correct Implementation:

def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    if root is None:
        return True
    # CORRECT - Compare left and right subtrees
    return is_mirror(root.left, root.right)

3. Incomplete Base Case Handling

A critical error is not properly handling all combinations of None nodes:

Incorrect Implementation:

def is_mirror(left_node, right_node):
    # WRONG - Missing the case where only one node is None
    if left_node is None and right_node is None:
        return True
  
    # This will cause AttributeError if one node is None
    if left_node.val != right_node.val:
        return False

Correct Implementation:

def is_mirror(left_node, right_node):
    # Handle both None
    if left_node is None and right_node is None:
        return True
  
    # Handle exactly one None - must check before accessing .val
    if left_node is None or right_node is None:
        return False
  
    # Now safe to access .val
    if left_node.val != right_node.val:
        return False

4. Using OR Instead of AND in Recursive Calls

Some developers mistakenly use or when combining recursive results:

Incorrect Implementation:

# WRONG - This would return True if only one side is symmetric
return (is_mirror(left_node.left, right_node.right) or 
        is_mirror(left_node.right, right_node.left))

Correct Implementation:

# CORRECT - Both sides must be symmetric
return (is_mirror(left_node.left, right_node.right) and 
        is_mirror(left_node.right, right_node.left))

5. Not Considering Single Node Trees

While the provided solution handles this correctly, a common oversight is not recognizing that a tree with just a root node (no children) is symmetric:

# Tree with just root node
root = TreeNode(1)  
# Should return True, as a single node is symmetric

The solution correctly handles this by checking if both root.left and root.right are None, which returns True.