Symmetric Tree

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?

Approach: Recursive Mirror Comparison (Optimal Solution)

Algorithm

1. Define a helper isMirror(root1, root2) that checks whether two trees mirror each other
2. Base cases:
   • If root1 == root2 (both null), return true
   • If either is null or their values differ, return false
3. Return isMirror(root1.left, root2.right) && isMirror(root1.right, root2.left)
4. The answer is isMirror(root.left, root.right)

Key Insight

A tree is symmetric if its left and right subtrees are mirror images: the left child of one subtree must correspond to the right child of the other. Instead of comparing a node with itself, we compare two nodes from opposite sides of the tree at every step.

Time & Space Complexity

• Time Complexity: O(n) - every node is visited once
• Space Complexity: O(n) - recursion stack in the worst case (a skewed tree)

Java Implementation

/**
 * Definition for a binary tree node.
 * public 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 class SymmetricTree {

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

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

Example Walkthrough

For root = [1,2,2,3,4,4,3]:

1. isMirror(2, 2): values equal, recurse
2. isMirror(2.left=3, 2.right=3): values equal, both children null → true
3. isMirror(2.right=4, 2.left=4): values equal, both children null → true
4. Both true, so the tree is symmetric

For root = [1,2,2,null,3,null,3] (level order: root 1, left 2, right 2, null, 3, null, 3):

1. Left subtree of root: node 2 with left=null, right=3
2. Right subtree of root: node 2 with left=null, right=3
3. isMirror(left2, right2): values equal, recurse crosswise
4. isMirror(left2.left=null, right2.right=3): null vs a node → false

So the tree is not symmetric. The 3 hangs off the right side of both children; for a mirror image it would need to hang off the left side of one of them. The mirror pairing is crosswise: root1.left ↔ root2.right.

Alternative Approach: Iterative BFS

import java.util.ArrayDeque;
import java.util.Deque;

public class SymmetricTreeIterative {

    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null || left.val != right.val) {
                return false;
            }
            queue.offer(left.left);
            queue.offer(right.right);
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

The iterative variant enqueues mirrored pairs (left.left with right.right, left.right with right.left) and processes them in the same crosswise fashion, avoiding recursion entirely.

Key Insights

1. Crosswise Comparison: root1.left mirrors root2.right, never root2.left
2. Two-Node Comparison: Comparing pairs of nodes from opposite subtrees is the core idea
3. Value Check First: Different values fail immediately without further recursion
4. Recursive and Iterative: Both approaches achieve O(n) time; recursion is cleaner, iteration avoids the stack

The recursive mirror comparison is the optimal solution, providing O(n) time and O(n) space.