Symmetric Tree

1. If the root is null, the tree is symmetric by definition, so return true.
2. Create a helper function isMirror(TreeNode t1, TreeNode t2) that takes two nodes and checks if the subtrees rooted at them are mirror images.
3. Base Cases for the recursion within isMirror:
   • If both t1 and t2 are null, they are symmetric. Return true.
   • If one of the nodes is null but the other isn't, they cannot be mirrors. Return false.
   • If the values of the nodes t1.val and t2.val are not equal, they are not mirrors. Return false.
4. Recursive Step: For the subtrees to be mirrors, the left child of t1 must be a mirror of the right child of t2, AND the right child of t1 must be a mirror of the left child of t2. The function should return the result of isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left).
5. The initial call from the isSymmetric function will be isMirror(root.left, root.right).

A tree is symmetric if the root is null or if its left and right subtrees are mirrors of each other. We can implement a helper function, say isMirror(t1, t2), which takes two nodes as input and returns true if the trees rooted at t1 and t2 are mirror images. The isMirror function works as follows:

1. If both t1 and t2 are null, they are symmetric. Return true.
2. If one of t1 or t2 is null (but not both), they are not symmetric. Return false.
3. If the values of t1 and t2 are different, they are not symmetric. Return false.
4. The crucial step is the recursive call: the structure is symmetric only if t1's left child is a mirror of t2's right child AND t1's right child is a mirror of t2's left child. So, we return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left).

The initial call from the main function isSymmetric will be isMirror(root.left, root.right).

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean isSymmetric(TreeNode root) {18        if (root == null) {19            return true;20        }21        return isMirror(root.left, root.right);22    }23 24    private boolean isMirror(TreeNode t1, TreeNode t2) {25        // Both are null, which is symmetric26        if (t1 == null && t2 == null) {27            return true;28        }29        // One is null, but not the other, not symmetric30        if (t1 == null || t2 == null) {31            return false;32        }33        // Values must be equal, and subtrees must be mirrors34        return (t1.val == t2.val)35            && isMirror(t1.right, t2.left)36            && isMirror(t1.left, t2.right);37    }38}

1. If the root is null, return true.
2. Initialize a Queue (e.g., a LinkedList) to store nodes for comparison.
3. Add the root's left child and right child to the queue. These are the first pair to be compared.
4. Start a loop that continues as long as the queue is not empty.
5. Inside the loop, dequeue two nodes, t1 and t2.
6. If both t1 and t2 are null, this pair is symmetric, so continue to the next iteration.
7. If one of the nodes is null (but not both), or if their values t1.val and t2.val are different, the tree is not symmetric. Return false.
8. If the nodes are valid so far, enqueue their children in a mirrored order for future comparison: add t1.left and t2.right to the queue, then add t1.right and t2.left.
9. If the loop completes without returning false, it means all corresponding nodes matched, and the tree is symmetric. Return true.

Instead of relying on the function call stack for recursion, we can use an explicit Queue to manage the pairs of nodes that need to be compared. This approach is often preferred to avoid potential stack overflow issues.

The algorithm works as follows:

1. Initialize a queue and add the root's left and right children. These are the first two nodes to compare.
2. Loop while the queue is not empty. In each step, we poll two nodes from the queue.
3. Let the two nodes be t1 and t2. We apply the same checks as in the recursive approach:
   • If both are null, they are symmetric, and we continue.
   • If one is null or their values differ, the tree is not symmetric, and we return false.
4. If the nodes t1 and t2 are a symmetric pair, we then add their children to the queue for the next level of checks. Crucially, we must add them in a mirrored order: t1.left is paired with t2.right, and t1.right is paired with t2.left.
5. If the queue becomes empty, it means we have successfully compared all the necessary pairs without finding any asymmetry, so the tree is symmetric.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public boolean isSymmetric(TreeNode root) {18        if (root == null) {19            return true;20        }21        Queue<TreeNode> queue = new LinkedList<>();22        queue.add(root.left);23        queue.add(root.right);24 25        while (!queue.isEmpty()) {26            TreeNode t1 = queue.poll();27            TreeNode t2 = queue.poll();28 29            if (t1 == null && t2 == null) {30                continue;31            }32            if (t1 == null || t2 == null) {33                return false;34            }35            if (t1.val != t2.val) {36                return false;37            }38 39            // Enqueue in mirrored order40            queue.add(t1.left);41            queue.add(t2.right);42            queue.add(t1.right);43            queue.add(t2.left);44        }45        return true;46    }47}