Algorithm-Day40-Symmetric-Tree-lc-101

Posted on In , Views:

🧩 Problem Description

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

💬 Example

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

Symmetric ✅

💡 Approach 1: Recursive Comparison

We define a helper function isMirror(left, right) to check whether two subtrees are mirror images of each other.

🔢 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
            && isMirror(t1.left, t2.right)
            && isMirror(t1.right, t2.left);
    }
}

💡 Approach 2: Iterative (BFS with Queue)

We can also use a queue to compare nodes level by level.

🔢 Java Code (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;

        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) return false;
            if (t1.val != t2.val) return false;

            queue.offer(t1.left);
            queue.offer(t2.right);
            queue.offer(t1.right);
            queue.offer(t2.left);
        }

        return true;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n) — visit each node once
  • Space Complexity:
    • Recursive: O(h)
    • Iterative: O(w) for queue

✍️ Summary

  • Use recursion for elegant, clear code.
  • Iterative is slightly more verbose but stack-safe.
  • Understand the mirror condition:
    • left.left == right.right
    • left.right == right.left

Often paired with lc-100, lc-226, and other binary tree symmetry/mirroring problems.