🌲 Symmetric Tree (LeetCode 101) — Recursive and Iterative Solutions Explained

Checking whether a binary tree is symmetric is a classic recursion problem — and a great way to learn how to traverse a tree in mirrored fashion. In this post, we'll cover both the recursive and iterative solutions to LeetCode 101 with clear explanations, diagrams, and code.

📌 Problem Statement

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

✅ Examples

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

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

---

🧠 Core Concept

A binary tree is symmetric if the left and right subtrees are mirror images of each other.

That means:

• left.left == right.right

• left.right == right.left

---

🔁 Recursive Solution (Top-Down Mirror Check)

💡 Idea

We define a helper function compare(left, right) that checks whether two subtrees are mirror images.

✅ Java Code

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);
    }

    private boolean compare(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 compare(left.left, right.right) && compare(left.right, right.left);
    }
}

---

🔍 Breakdown

At each node, we check:

1. If both nodes are null: ✔️ symmetric

2. If only one is null: ❌ not symmetric

3. If values differ: ❌ not symmetric

4. Recursively check:

   • Outer pair: left.left vs right.right

   • Inner pair: left.right vs right.left

---

🔄 Iterative Solution Using Deque

💡 Idea

We simulate the comparison of mirrored nodes using a double-ended queue (Deque):

• Enqueue left to the front

• Enqueue right to the back

• Pop them and compare, then enqueue their child nodes in mirrored order

✅ Java Code

class Solution {
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root.left);
        deque.offerLast(root.right);

        while (!deque.isEmpty()) {
            TreeNode left = deque.pollFirst();
            TreeNode right = deque.pollLast();

            if (left == null && right == null) continue;
            if (left == null || right == null || left.val != right.val) return false;

            // Mirror order insert
            deque.addFirst(left.left);
            deque.addFirst(left.right);
            deque.addLast(right.right);
            deque.addLast(right.left);
        }

        return true;
    }
}

---

🔁 Visual

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

Check:

• (2, 2)

• (3, 3) and (4, 4)

• Each level mirrors the other

---

🧠 Time and Space Complexity

• n = number of nodes

• h = height of tree

---

✅ Summary

---

🧘 Takeaways

• Symmetric trees = mirrored traversal

• Recursive and iterative solutions follow the same mirror pattern logic

• Always check null before accessing .val to avoid NPE

---

✍️ My Practice Notes

• Solved using both approaches

• Time taken: ~10 mins

• Could easily explain this in a real interview

---

📎 Related Problems

• 100. Same Tree

• 226. Invert Binary Tree

• 110. Balanced Binary Tree