L25: Check for Symmetrical Binary Trees

1. Introduction and Problem Statement

A binary tree is said to be symmetric (or a folding mirror of itself) if it forms an exact mirror image of itself around its center root. When you draw a vertical line down the middle from the root node, the left subtree must be a complete mirror reflection of the right subtree.

       1                  1
     /   \              /   \
    2     2            2     2
   / \   / \            \     \
  3   4 4   3            3     3
  
(Symmetric Tree)     (Non-Symmetric Tree)

In the first tree, if you take the left half and fold/impose it onto the right half, node 3 matches 3, and node 4 matches 4. In the second tree, although values appear balanced, the structural positions fail the mirror condition.

2. The Real-Life Analogy: Standing Before a Mirror

Real-Life Analogy: Think of standing in front of a mirror with your hands outstretched. Your left hand in the real world corresponds to the right hand visible in the reflection. Similarly, the mirror reflection inverts directions: what is on the left side of the mirror world looks toward the right side of the real world.

Applying this to binary trees:

• If we traverse the left subtree, we move in a standard pattern: Root -> Left -> Right.
• To check for symmetry, the corresponding traversal on the right subtree must mirror this movement: Root -> Right -> Left.

3. Naive vs. Optimal Approach

• Naive Approach (Inversion then Comparison): You might think of taking the left or right subtree, creating a brand-new inverted tree, and then comparing it node-by-node with the other subtree.
  • Drawback: This requires extra memory to build a duplicate cloned tree, increasing space complexity unnecessarily and complicating implementation.
• Optimal Approach (Simultaneous Mirror Traversal): Instead of cloning or modifying trees, we pass two pointers (leftNode and rightNode) starting right below the root and walk through both subtrees simultaneously in mirrored directions.

4. Core Mental Model: Simultaneous Dual-Pointer Traversal

To validate symmetry, our algorithm must inspect nodes at corresponding mirror positions at the exact same time.

As we traverse:

1. Compare leftNode.val with rightNode.val.
2. Recursively check outer boundaries: leftNode.left against rightNode.right.
3. Recursively check inner boundaries: leftNode.right against rightNode.left.

5. Step-by-Step Flow Walkthrough

Let's trace how the algorithm validates a valid symmetric tree:

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

1. Initial Check: Verify root is not null. Pass root.left (Left Node 2) and root.right (Right Node 2) into our helper function isSymmetric(left, right).
2. First Comparison: Compare values 2 and 2. They match.
3. Outer Recursive Call: Compare outer children -> left.left (3) and right.right (3). Values match.
   • Next, compare their children (3.left with 3.right and 3.right with 3.left), both encounter null == null (returns true).
4. Inner Recursive Call: Compare inner children -> left.right (4) and right.left (4). Values match.
   • Next, compare their children, both encounter null == null (returns true).
5. Result: All simultaneous checks pass. Return true.

6. Edge Cases and Handling

When designing recursive tree checks, base conditions prevent runtime exceptions (NullPointerException):

7. Implementation Code (C++ and Java)

C++ Implementation

class Solution {
private:
    bool helper(TreeNode* leftTree, TreeNode* rightTree) {
        // Base case: both pointers reach null
        if (leftTree == nullptr && rightTree == nullptr) return true;
        
        // If only one is null, or values don't match, it's not symmetric
        if (leftTree == nullptr || rightTree == nullptr || leftTree->val != rightTree->val) 
            return false;
        
        // Simultaneously check outer and inner subtrees
        return helper(leftTree->left, rightTree->right) && 
               helper(leftTree->right, rightTree->left);
    }

public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return helper(root->left, root->right);
    }
};

Java Implementation

class Solution {
    private boolean helper(TreeNode leftTree, TreeNode rightTree) {
        // Base case: both pointers reach null
        if (leftTree == null && rightTree == null) return true;
        
        // If only one is null, or values don't match, it's not symmetric
        if (leftTree == null || rightTree == null || leftTree.val != rightTree.val) 
            return false;
        
        // Simultaneously check outer and inner subtrees
        return helper(leftTree.left, rightTree.right) && 
               helper(leftTree.right, rightTree.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return helper(root.left, root.right);
    }
}

8. Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$
  • Every node in the binary tree is visited exactly once during the simultaneous traversal (where $N$ is the total number of nodes).
• Space Complexity: $\mathcal{O}(N)$ in the worst-case scenario.
  • Recursion stack space depends on the height of the tree. For a completely skewed tree (degenerate tree), the height becomes $N$, resulting in $\mathcal{O}(N)$ stack memory. For a balanced tree, space complexity is $\mathcal{O}(\log N)$.

9. Summary and Key Takeaways

• Definition of Symmetry: A symmetric binary tree is its own mirror image around the central root axis.
• Mirror Logic Inversion: Left-to-right traversal on one side must be matched with right-to-left traversal on the opposite side.
• Dual-Pointer Technique: Rather than modifying or cloning trees, pass left.left with right.right (outer nodes) and left.right with right.left (inner nodes) recursively.
• Base Conditions Matter: Always handle simultaneous null checks first to prevent segmentation faults or NullPointerExceptions.
• Optimal Efficiency: Achieves optimal $\mathcal{O}(N)$ time complexity with zero auxiliary data structures needed beyond recursive call stack frames.