Symmetric Tree

Description

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 1: Recursive DFS ($O(N)$ Time, $O(H)$ Space)

Intuition

A binary tree is symmetric if its left and right subtrees are mirror images of each other. Two subtrees $T_1$ and $T_2$ are mirrors if:

1. Their root values are equal (t1.val == t2.val).
2. $T_1$’s left child is a mirror of $T_2$‘s right child (t1.left vs t2.right).
3. $T_1$’s right child is a mirror of $T_2$‘s left child (t1.right vs t2.left).

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }
 
    private boolean isMirror(TreeNode t1, TreeNode t2) {
        // Base cases
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null || t1.val != t2.val) return false;
 
        // Compare outer pair (t1.left, t2.right) and inner pair (t1.right, t2.left)
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — We visit every node in the binary tree at most once.
• Space Complexity: $O(H)$ — Bounded by the height of the recursion stack $H$ ($O(\log N)$ for a balanced tree, $O(N)$ for a skewed tree).

---

Approach 2: Iterative BFS ($O(N)$ Time, $O(N)$ Space)

Intuition

Simulate the mirror check iteratively using a Queue (LinkedList handles null values cleanly):

1. Offer root.left and root.right as the initial pair into the queue.
2. In each iteration, poll two nodes t1 and t2:
   • If both are null, continue.
   • If one is null or t1.val != t2.val, return false.
3. Push corresponding mirror pairs side-by-side:
   • Outer pair: t1.left and t2.right
   • Inner pair: t1.right and t2.left

import java.util.LinkedList;
import java.util.Queue;
 
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
 
        // LinkedList allows null elements required for structural checks
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
 
        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
 
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null || t1.val != t2.val) return false;
 
            // Enqueue outer children together
            queue.offer(t1.left);
            queue.offer(t2.right);
 
            // Enqueue inner children together
            queue.offer(t1.right);
            queue.offer(t2.left);
        }
 
        return true;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each node is enqueued and polled once.
• Space Complexity: $O(N)$ — Queue holds at most one level of nodes at a time (up to $N/2$ nodes).

---

Easy Memory Rule

“Compare outer children together (t1.left & t2.right) and inner children together (t1.right & t2.left)!”