1. What Is a Symmetric Tree?

A symmetric tree is a binary tree that is a mirror image of itself around its center.

2. Visual Example of a Symmetric Tree

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

The left subtree is a mirror reflection of the right subtree.

3. Visual Example of an Asymmetric Tree

  1
 / \
2   2
 \   \
 3    3

Here, symmetry is broken because one node has a right child and the other has none.

4. Symmetric vs Mirror Image

• Symmetric Tree: A tree is symmetric about its root.
• Mirror Trees: Two trees are mirror images of each other.

So the symmetric tree problem is essentially:
Are the left and right subtrees mirror images?

5. Problem Statement

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

Constraints:

• The number of nodes in the tree is in the range [0, 1000].
• -100 <= Node.val <= 100

6. Recursive Approach

Key Idea:

Compare the left and right subtrees of the root and check:

• Root values are equal.
• Left child of left subtree == right child of right subtree.
• Right child of left subtree == left child of right subtree.

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class SymmetricTree {

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

7. Iterative Approach Using Queue

Use a queue to simulate a breadth-first traversal comparing node pairs.

Enqueue the left and right nodes of the root.
While the queue is not empty:

• Dequeue two nodes.
• If both null → continue.
• If only one null or values differ → not symmetric.
• Enqueue children in mirrored order:
  • t1.left and t2.right
  • t1.right and t2.left

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

public class SymmetricTree {

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

        Queue<TreeNode> q = new LinkedList<>();
        q.add(root.left);
        q.add(root.right);

        while (!q.isEmpty()) {
            TreeNode t1 = q.poll();
            TreeNode t2 = q.poll();

            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null || t1.val != t2.val) return false;

            q.add(t1.left);
            q.add(t2.right);

            q.add(t1.right);
            q.add(t2.left);
        }

        return true;
    }
}

8. Compare two different trees as mirrors

public boolean isMirrorTree(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val &&
           isMirrorTree(a.left, b.right) &&
           isMirrorTree(a.right, b.left);
}