Skip to content

132. Symmetric Tree

🔗 LeetCode Problem: 101. Symmetric Tree
📊 Difficulty: Easy
🏷️ Topics: Binary Trees, Recursion, DFS, BFS

Problem Statement

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

🌳 Visual Understanding - Drawing the Trees First!

Let's visualize what "symmetric" means for a tree.

Example 1: Symmetric Tree ✓

Input: [1,2,2,3,4,4,3]

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

Is this symmetric? YES! ✓

Let's see the mirror:
        1
       / \
      2   2      ← These mirror each other
     / \ / \
    3  4 4  3    ← Left side mirrors right side

Mirror line (vertical):
        1
        |
      2 | 2
     /| |\ \
    3 4| 4 3
       |
    Left = Right (mirrored)

Example 2: NOT Symmetric ✗

Input: [1,2,2,null,3,null,3]

        1
       / \
      2   2
       \   \
        3   3

Is this symmetric? NO! ✗

Why not?
        1
       / \
      2   2
       \   \      ← Left has right child
        3   3     ← Right has right child
                  ← These DON'T mirror!

Left side:        Right side:
    2                 2
     \                 \
      3                 3

For mirror, if left has RIGHT child,
right should have LEFT child!

What Makes a Tree Symmetric?

A tree is symmetric if:
  1. The root's left subtree is a mirror of the root's right subtree

A subtree A is a mirror of subtree B if:
  1. A and B have the same value (A.val == B.val)
  2. A's LEFT is mirror of B's RIGHT
  3. A's RIGHT is mirror of B's LEFT

Notice the swap: LEFT ↔ RIGHT

More Examples:

Example 3: Single node
    1

Symmetric? YES! ✓
(Empty left mirrors empty right)

Example 4: Two nodes
    1
   /
  2

Symmetric? NO! ✗
(Left has 2, right has null)

Example 5: Perfect mirror
    1
   / \
  2   2

Symmetric? YES! ✓
(Both sides have same value, no children)

Example 6: Values match but structure doesn't
      1
     / \
    2   2
   /     \
  3       3

Symmetric? NO! ✗
(Left has left child, right has right child - not mirrored!)

🧠 The AHA Moment - Connecting to Problem 131!

Remember Problem 131 (Same Tree)?

Problem 131: Are two trees THE SAME?
  isSameTree(p, q):
    - p.val == q.val
    - p.left same as q.left
    - p.right same as q.right

Problem 132: Are two trees MIRRORS?
  isMirror(p, q):
    - p.val == q.val
    - p.left mirrors q.RIGHT  ← Swap!
    - p.right mirrors q.LEFT   ← Swap!

The only difference: We compare LEFT with RIGHT (and vice versa)!

Visual Comparison:

Same Tree:
    p:  1        q:  1
       / \          / \
      2   3        2   3

    Compare:
      p.left (2) with q.left (2) ✓
      p.right (3) with q.right (3) ✓

Mirror Tree:
    p:  1        q:  1
       / \          / \
      2   3        3   2

    Compare:
      p.left (2) with q.RIGHT (2) ✓
      p.right (3) with q.LEFT (3) ✓

🧠 Recursive Thinking - Building the Solution

The Key Insight:

To check if a tree is symmetric:
  1. Check if left subtree mirrors right subtree
  2. Use a helper function: isMirror(left, right)

Base Cases for isMirror(left, right):

Base Case 1: Both null
  isMirror(null, null) → true
  WHY? Two empty trees mirror each other

Base Case 2: One null, other not
  isMirror(null, node) → false
  isMirror(node, null) → false
  WHY? Different structure, can't mirror

Base Case 3: Different values
  isMirror(left, right) where left.val ≠ right.val → false
  WHY? Even if structure mirrors, values must match

Recursive Case:

If we reach here:
  - Both nodes exist (not null)
  - Both nodes have same value

Check if subtrees mirror:
  1. left.left mirrors right.right ✓
  2. left.right mirrors right.left ✓

Notice the CROSS pattern:
     left           right
      / \            / \
     L   R          R'  L'

  Compare: L with R' (outer pair)
  Compare: R with L' (inner pair)

The Recursion Formula:

isMirror(left, right):
  // Base cases
  if (both null) return true
  if (one null) return false
  if (values differ) return false

  // Recursive case: Check cross pattern
  return isMirror(left.left, right.right) &&   // Outer pair
         isMirror(left.right, right.left)      // Inner pair

🎯 Solution 1: Recursive DFS (Most Natural)

The Complete Solution

class Solution {
    public boolean isSymmetric(TreeNode root) {
        // A tree is symmetric if left subtree mirrors right subtree
        // Edge case: null tree is symmetric
        if (root == null) {
            return true;
        }

        // Check if left and right subtrees are mirrors
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        // Base Case 1: Both nodes are null
        // WHY? Two empty subtrees are mirrors of each other
        if (left == null && right == null) {
            return true;
        }

        // Base Case 2: One node is null, the other is not
        // WHY? Different structure means not mirrored
        if (left == null || right == null) {
            return false;
        }

        // Base Case 3: Node values are different
        // WHY? Mirror requires same values at mirrored positions
        if (left.val != right.val) {
            return false;
        }

        // Recursive Case: Check the cross pattern
        // WHY? For mirror symmetry:
        //   - left's LEFT must mirror right's RIGHT (outer pair)
        //   - left's RIGHT must mirror right's LEFT (inner pair)
        return isMirror(left.left, right.right) &&   // Outer
               isMirror(left.right, right.left);     // Inner
    }
}

Understanding the Cross Pattern:

Why do we compare left.left with right.right?

Visualize the mirror:
        root
       /    \
    left    right
     / \     / \
    A   B   C   D

For symmetry:
  A must mirror D (leftmost mirrors rightmost)
  B must mirror C (inner left mirrors inner right)

Hence:
  left.left (A) with right.right (D) ✓
  left.right (B) with right.left (C) ✓

🔍 Detailed Dry Run with Recursion Visualization

Let's trace through Example 1 step by step.

Input Tree:
        1
       / \
      2   2
     / \ / \
    3  4 4  3

The Complete Recursion Call Tree:

MAIN CALL:
isSymmetric(root=1)
  └─ calls isMirror(root.left=2, root.right=2)

RECURSION TREE:

Level 0: isMirror(left=2, right=2)
│
├─ Values: 2 == 2 ✓
├─ Both not null ✓
│
├─ OUTER PAIR: isMirror(left.left, right.right) ─────┐
│                                                      │
│  Level 1: isMirror(left=3, right=3)                │
│  │                                                   │
│  ├─ Values: 3 == 3 ✓                               │
│  ├─ Both not null ✓                                 │
│  │                                                   │
│  ├─ OUTER: isMirror(left.left=null, right.right=null)
│  │  Level 2: Both null → return true ✓             │
│  │                                                   │
│  └─ INNER: isMirror(left.right=null, right.left=null)
│     Level 2: Both null → return true ✓             │
│                                                      │
│  Result: true && true = true ✓                     │
│                                                      │
├─ INNER PAIR: isMirror(left.right, right.left) ─────┐
│                                                      │
│  Level 1: isMirror(left=4, right=4)                │
│  │                                                   │
│  ├─ Values: 4 == 4 ✓                               │
│  ├─ Both not null ✓                                 │
│  │                                                   │
│  ├─ OUTER: isMirror(left.left=null, right.right=null)
│  │  Level 2: Both null → return true ✓             │
│  │                                                   │
│  └─ INNER: isMirror(left.right=null, right.left=null)
│     Level 2: Both null → return true ✓             │
│                                                      │
│  Result: true && true = true ✓                     │
│                                                      │
└─ FINAL: true && true = true ✓

OUTPUT: true

Visual Representation of Comparisons:

Tree:
        1
       / \
      2   2        ← Comparing these two nodes
     / \ / \
    3  4 4  3

Step 1: Compare (2, 2)
  Values match ✓

  Now check children in CROSS pattern:

        2       2
       / \     / \
      3   4   4   3
      ↓   X   X   ↓
      └───┼───┼───┘
          └───┘

  Outer: (3, 3) ✓
  Inner: (4, 4) ✓

Step 2: Compare (3, 3) [Outer pair]
  Values match ✓
  Both have no children → true ✓

Step 3: Compare (4, 4) [Inner pair]
  Values match ✓
  Both have no children → true ✓

All comparisons pass → Symmetric! ✓

Step-by-Step Call Stack:

Call Stack (growing down):

Depth 0: isMirror(2, 2)
         ├─ Check outer...

Depth 1:   isMirror(3, 3)
           ├─ Check outer...

Depth 2:     isMirror(null, null) → true ✓

Depth 2:     isMirror(null, null) → true ✓

Depth 1:   Returns true ✓

Depth 0: ├─ Check inner...

Depth 1:   isMirror(4, 4)
           ├─ Check outer...

Depth 2:     isMirror(null, null) → true ✓

Depth 2:     isMirror(null, null) → true ✓

Depth 1:   Returns true ✓

Depth 0: Returns true ✓

Final: true

📊 Example 2 Dry Run - Not Symmetric

Input Tree:
        1
       / \
      2   2
       \   \
        3   3

Main: isMirror(left=2, right=2)

Recursion Flow:

Level 0: isMirror(left=2, right=2)
│
├─ Values: 2 == 2 ✓
├─ Both not null ✓
│
├─ OUTER PAIR: isMirror(left.left, right.right)
│              isMirror(null, null) → true ✓
│
├─ INNER PAIR: isMirror(left.right, right.left)
│              isMirror(3, null)
│              └─ One is null, one is not
│                 return false ✗
│
└─ Result: true && false = false ✗

OUTPUT: false ✗

WHY IT FAILS:
Visual:
    2       2
     \       \
      3       3

Left has RIGHT child (3)
Right has RIGHT child (3)

For mirror:
  If left has RIGHT child,
  right should have LEFT child!

  But right has RIGHT child → Not mirrored!

🎯 Solution 2: Iterative DFS (Using Stack)

We can solve this iteratively using a stack!

The Idea:

Instead of recursion, use a stack to track pairs of nodes to compare
Push pairs in the CROSS pattern

Implementation:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        // Stack stores pairs of nodes to compare
        Stack<TreeNode> stack = new Stack<>();

        // Start by comparing left and right subtrees
        stack.push(root.left);
        stack.push(root.right);

        while (!stack.isEmpty()) {
            // Pop two nodes to compare
            TreeNode right = stack.pop();
            TreeNode left = stack.pop();

            // Both null - continue
            if (left == null && right == null) {
                continue;
            }

            // One null, one not - not symmetric
            if (left == null || right == null) {
                return false;
            }

            // Different values - not symmetric
            if (left.val != right.val) {
                return false;
            }

            // Push children in CROSS pattern
            // IMPORTANT: Push in pairs!

            // Outer pair: left.left with right.right
            stack.push(left.left);
            stack.push(right.right);

            // Inner pair: left.right with right.left
            stack.push(left.right);
            stack.push(right.left);
        }

        return true;
    }
}

Why This Works:

Stack stores pairs of nodes that should mirror each other

Example:
        1
       / \
      2   2
     / \ / \
    3  4 4  3

Iteration 1:
  Pop: (2, 2)
  Check: Values match ✓
  Push: (3, 3) - outer pair
  Push: (4, 4) - inner pair
  Stack: [(3,3), (4,4)]

Iteration 2:
  Pop: (4, 4)
  Check: Values match ✓
  Push: (null, null), (null, null)
  Stack: [(3,3), (null,null), (null,null)]

Iteration 3:
  Pop: (null, null)
  Check: Both null, continue ✓
  Stack: [(3,3), (null,null)]

Iteration 4:
  Pop: (null, null)
  Check: Both null, continue ✓
  Stack: [(3,3)]

Iteration 5:
  Pop: (3, 3)
  Check: Values match ✓
  Push: (null, null), (null, null)
  Stack: [(null,null), (null,null)]

Iteration 6-7:
  Pop and check nulls
  Stack: []

Result: true ✓

Critical: Push Order Matters!

// ✓ CORRECT - Pairs stay together
stack.push(left.left);
stack.push(right.right);  // Paired with left.left
stack.push(left.right);
stack.push(right.left);   // Paired with left.right

When we pop:
  right.left comes first
  left.right comes second
  → Correct pair! ✓

// ❌ WRONG - Pairs get mixed up
stack.push(left.left);
stack.push(left.right);
stack.push(right.left);
stack.push(right.right);

When we pop:
  right.right comes first
  right.left comes second
  → Wrong pairing! ✗

🎯 Solution 3: BFS (Level Order Traversal)

We can also use BFS with a queue!

Implementation:

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        // Start with left and right subtrees
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()) {
            // Poll two nodes to compare
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            // Both null - continue
            if (left == null && right == null) {
                continue;
            }

            // One null, one not - not symmetric
            if (left == null || right == null) {
                return false;
            }

            // Different values - not symmetric
            if (left.val != right.val) {
                return false;
            }

            // Enqueue children in CROSS pattern
            // Outer pair
            queue.offer(left.left);
            queue.offer(right.right);

            // Inner pair
            queue.offer(left.right);
            queue.offer(right.left);
        }

        return true;
    }
}

BFS vs DFS:

Both work identically for this problem!

BFS (Queue):
  - Checks level by level
  - Might find asymmetry faster if it's near root
  - Same time/space complexity

DFS (Stack/Recursion):
  - Goes deep first
  - Slightly more intuitive for trees
  - Recursive version is cleanest

For symmetric tree: Use whichever you prefer!
I recommend: Recursive DFS (cleanest code)

📊 Complexity Analysis

Recursive Solution:

Time Complexity: O(n) 

Where n = number of nodes in the tree

Why?
  - We visit each node exactly once
  - Each node is compared exactly once
  - No node is visited multiple times

Example:
  Tree with 7 nodes:
    Comparisons: root, (2,2), (3,3), (4,4), nulls
    Total: O(n) operations

Space Complexity: O(h) 

Where h = height of the tree

Why?
  - Recursion call stack depth
  - Maximum depth = height of tree

Best case (balanced tree): O(log n)
  Height of balanced tree with n nodes ≈ log₂(n)

Worst case (skewed tree): O(n)
  Example:
      1
     /
    2
   /
  3
  Height = n → Space = O(n)

For symmetric tree check:
  - Likely balanced (symmetric trees are often balanced)
  - Space usually O(log n)

Iterative Solutions:

Time Complexity: O(n) - Same as recursive

Space Complexity: O(n) in worst case 

Why potentially more than recursive?

Stack/Queue can hold multiple nodes at once

Worst case: Complete binary tree
  Bottom level has n/2 nodes
  Queue could hold up to n/2 pairs
  Space: O(n)

vs Recursive:
  Call stack holds one path at a time
  Depth = height = O(log n) for balanced tree

Trade-off:
  Recursive: Better space for balanced trees
  Iterative: Avoids stack overflow for deep trees

⚠️ Common Mistakes with Symmetric Trees

Mistake 1: Comparing Left with Left (Instead of Cross)

// ❌ WRONG - Comparing same sides!
private boolean isMirror(TreeNode left, TreeNode right) {
    // ...
    return isMirror(left.left, right.left) &&    // Wrong!
           isMirror(left.right, right.right);    // Wrong!
}

// This checks if trees are SAME, not MIRROR!

// ✓ CORRECT - Cross pattern
private boolean isMirror(TreeNode left, TreeNode right) {
    // ...
    return isMirror(left.left, right.right) &&   // Cross!
           isMirror(left.right, right.left);     // Cross!
}

Mistake 2: Forgetting the Helper Function

// ❌ WRONG - Trying to solve without helper
public boolean isSymmetric(TreeNode root) {
    // How do we compare left with right subtree?
    // Need TWO parameters, but we only have ONE root!
    return isMirror(root.left, root.right);  // Where's this function?
}

// ✓ CORRECT - Use helper function
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);  // Helper with 2 params
}

private boolean isMirror(TreeNode left, TreeNode right) {
    // Now we can compare two nodes!
}

Mistake 3: Not Handling Null Root

// ❌ WRONG - NullPointerException for null tree
public boolean isSymmetric(TreeNode root) {
    return isMirror(root.left, root.right);  // Crash if root==null!
}

// ✓ CORRECT - Check null root first
public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;  // Null tree is symmetric
    return isMirror(root.left, root.right);
}

Mistake 4: Wrong Push Order in Stack

// ❌ WRONG - Pairs get separated
stack.push(left.left);
stack.push(left.right);   // These two are NOT a pair!
stack.push(right.left);
stack.push(right.right);

// When we pop, we get wrong comparisons!

// ✓ CORRECT - Push in pairs
stack.push(left.left);
stack.push(right.right);  // Paired together ✓
stack.push(left.right);
stack.push(right.left);   // Paired together ✓

Mistake 5: Thinking Single Node is Not Symmetric

// ❌ WRONG THINKING
Tree: [1]
"Left is null, right is null, they're different!"
Result: false ✗

// ✓ CORRECT THINKING
Tree: [1]
"Both left and right are null → they mirror each other!"
Result: true ✓

// A single node (or null tree) IS symmetric!

🎯 Pattern Recognition - The Mirror Pattern

This problem introduces the Mirror Comparison pattern!

Core Pattern: Mirror Two Trees

Template for checking if two trees are mirrors:

isMirror(tree1, tree2):
  1. Base cases:
     - Both null → true
     - One null → false
     - Values differ → false

  2. Recursive case (CROSS pattern):
     - tree1.left mirrors tree2.RIGHT
     - tree1.right mirrors tree2.LEFT

  return isMirror(tree1.left, tree2.right) &&
         isMirror(tree1.right, tree2.left)

Comparison with Problem 131:

Problem 131 (Same Tree):
  Compare tree1.left with tree2.left
  Compare tree1.right with tree2.right
  → Parallel comparison

Problem 132 (Symmetric Tree):
  Compare tree1.left with tree2.RIGHT
  Compare tree1.right with tree2.LEFT
  → Cross comparison

Same structure, different comparison order!

1. Invert Binary Tree (Problem 136) 

Swap left and right at each node
After inversion, tree mirrors its original
Related concept: Tree mirroring

2. Flip Equivalent Binary Trees 

Check if two trees are same after flipping children
Uses mirror logic

3. Maximum Depth of Binary Tree (Problem 133) 

Uses similar recursion pattern:
  - Base case: null
  - Recursive: process left and right
  - Combine: max(left, right) + 1

When to Use Mirror Pattern:

✓ Checking tree symmetry
✓ Comparing trees with flipped structure
✓ Problems involving left-right swaps
✓ Tree reflection problems

📝 Quick Revision Notes

🎯 Core Concept

A tree is symmetric if its left subtree mirrors its right subtree. Use a helper function isMirror(left, right) that compares two trees in a CROSS pattern: left's left with right's right (outer), left's right with right's left (inner). Key difference from "same tree": cross comparison instead of parallel.

⚡ Quick Implementation

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

private boolean isMirror(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    if (left.val != right.val) return false;
    return isMirror(left.left, right.right) &&    // Outer
           isMirror(left.right, right.left);      // Inner
}

🔑 Key Insights

The Cross Pattern: 

     left       right
      / \        / \
     A   B      C   D

Mirror requires:
  A mirrors D (left.left with right.right)
  B mirrors C (left.right with right.left)

NOT:
  A with C (left.left with right.left) ✗

Helper Function is Essential: 

Main function: 1 parameter (root)
Need to compare: 2 parameters (left, right)

Solution: Helper function!
  isSymmetric(root) → calls isMirror(left, right)

Base Cases (Same as Problem 131): 

1. Both null → true
2. One null → false
3. Values differ → false
4. Recurse with cross pattern

🎪 Memory Aid

"Same tree = parallel, Mirror tree = cross"
"Left's left meets right's right"
"Left's right meets right's left"
"Always use helper for two-tree comparison!" ✨

⚠️ Don't Forget

  • Use helper function (need 2 parameters!)
  • Cross pattern for mirroring (not parallel!)
  • Check null root in main function
  • Base cases same as Problem 131
  • Push in pairs for iterative (stack order matters!)
  • Single node IS symmetric (both children null)

🔗 Pattern Template

// Template for comparing two trees (same or mirror)

import java.util.Stack;

import java.util.LinkedList;
import java.util.Queue;

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;
    }

    public static TreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0 || arr[0] == null) {
            return null;
        }

        TreeNode root = new TreeNode(arr[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while (!queue.isEmpty() && i < arr.length) {
            TreeNode current = queue.poll();

            // Process left child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.left = new TreeNode(arr[i]);
                    queue.offer(current.left);
                }
                i++;
            }

            // Process right child
            if (i < arr.length) {
                if (arr[i] != null) {
                    current.right = new TreeNode(arr[i]);
                    queue.offer(current.right);
                }
                i++;
            }
        }

        return root;
    }    
}

class Solution {
  public boolean isSymmetric(TreeNode root) {
    if(root == null) {
      return true;
    }

    // Key cencept:
    // Exactly same as "same tree" problem.
    // Instead of comparing same node on 2 trees, we need to compare symmetrically on same tree.
    // It means, compare left most node to right most node and compare middle nodes.
    // Root has (p, q). Have to compare p and q
    // p has p1 (left) and p2 (right). And q has q1 (left) and q2 (right)
    // We have to compare (p1 and q2) AND (p2 and q1)
    // Otherwise, all 3 methods are exactly same structure as "same tree". Change highlighted.

    // Approach 1 - Recursive DFS.
    return recursiveDFS(root.left, root.right);

    // // Approach 2 - Iterative DFS using Stack.
    // return iterativeDFS(root.left, root.right);

    // // Approach 3 - Iterative BFS using queue.
    // return iterativeBFS(root.left, root.right);
  }

  private boolean iterativeBFS(TreeNode p, TreeNode q) {
    Queue<TreeNode[]> queue = new LinkedList<>();
    queue.offer(new TreeNode[] {p, q});

    while (!queue.isEmpty()) {
      TreeNode[] polled = queue.poll();
      TreeNode pp = polled[0];
      TreeNode qq = polled[1];

      // case 1 - check for next element on the stack.
      if(pp == null && qq == null) {
        continue;
      }

      // case 2 - only 1 reached
      if(pp == null || qq == null) {
        return false;
      }

      // normal check at the current node
      if(pp.val != qq.val) {
        return false;
      }

      // Push the children of current nodes to the stack for next comparison.
      queue.offer(new TreeNode[] {pp.left, qq.right}); // CHANGE
      queue.offer(new TreeNode[] {pp.right, qq.left}); // CHANGE
    }

    return true;
  }

  private boolean iterativeDFS(TreeNode p, TreeNode q) {
    Stack<TreeNode[]> stack = new Stack<>();
    stack.push(new TreeNode[] {p, q}); // roots are pushed

    while (!stack.isEmpty()) {
      TreeNode[] popped = stack.pop();
      TreeNode pp = popped[0];
      TreeNode qq = popped[1];

      // case 1 - check for next element on the stack.
      if(pp == null && qq == null) {
        continue;
      }

      // case 2 - only 1 reached
      if(pp == null || qq == null) {
        return false;
      }

      // normal check at the current node
      if(pp.val != qq.val) {
        return false;
      }

      // Push the children of current nodes to the stack for next comparison.
      stack.push(new TreeNode[] {pp.left, qq.right}); // CHANGE
      stack.push(new TreeNode[] {pp.right, qq.left}); // CHANGE
    }

    return true;
  }

  private boolean recursiveDFS(TreeNode p, TreeNode q) {
    // base case 1 - reached leaf nodes.
    if(p == null && q == null) {
      return true;
    }

    // base case 2 - only 1 reached
    if(p == null || q == null) {
      return false;
    }

    // normal check at the current node
    if(p.val != q.val) {
      return false;
    }

    // check child nodes now - ONLY CHANGE
    return recursiveDFS(p.left, q.right) && recursiveDFS(p.right, q.left);
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.isSymmetric(TreeNode.buildTree(new Integer[] {1,2,2,3,4,4,3})));
    System.out.println(s.isSymmetric(TreeNode.buildTree(new Integer[] {1,2,2,null,3,null,3})));
  }
}

🎉 Congratulations!

You've mastered the Mirror Pattern in trees!

What You Learned:

✅ Mirror vs Same - Cross pattern vs parallel pattern
✅ Helper functions - When and why to use them
✅ Cross comparisons - Left with right, right with left
✅ Visual mirroring - Drawing and seeing symmetry
✅ Multiple approaches - Recursive, iterative DFS, BFS
✅ Common mistakes - Push order, cross pattern, helpers

Connection to Problem 131:

Problem 131 (Same Tree):
  isSameTree(p, q):
    return same(p.left, q.left) && same(p.right, q.right)
    → Parallel comparison

Problem 132 (Symmetric Tree):
  isMirror(left, right):
    return mirror(left.left, right.right) && mirror(left.right, right.left)
    → Cross comparison

Almost identical, just swapped the comparison!

Next Steps:

Try these to reinforce the pattern: - Problem 133: Maximum Depth (similar recursion structure) - Problem 136: Invert Binary Tree (uses mirroring concept!) - Problem 226: Flip Equivalent Binary Trees (advanced mirror pattern)

Happy tree mirroring! 🌳🪞✨