✅ 🔥 0 ms Runtime Beats 100% User🔥||  Code Idea ✅ ||  Algorithm & Solving Step  ✅ ||
\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n\n### Key Idea :\nA binary tree is symmetric if:\n1. Its left and right subtrees hav
![Screenshot 2024-11-28 at 8.25.14\u202FAM.png](https://assets.leetcode.com/users/images/2bcc33e0-e4e8-4bd8-831e-6f556e7eee44_1732763144.7556474.png)\n\n\u2705  IF YOU LIKE THIS SOLUTION, PLEASE UPVOTE AT THE END \u2705 :\n\n\n### **Key Idea** :\nA binary tree is symmetric if:\n1. Its left and right subtrees have the same structure.\n2. The values in the left and right subtrees mirror each other.\n\n---\n\n### **Approach** :\n\nWe can solve this using **recursion** or **iteration**:\n1. **Recursive Approach**:\n   - Compare the left and right subtrees of the root.\n   - For two subtrees to be mirrors:\n     - Their root values must be equal.\n     - The left subtree of one must be a mirror of the right subtree of the other, and vice versa.\n   - Recursively check this condition for all nodes.\n\n2. **Iterative Approach**:\n   - Use a queue to perform a level-order traversal, checking symmetry at each level.\n   - Push pairs of nodes to the queue for comparison.\n\n---\n\n### **Algorithm** :\n\n#### Recursive\n1. If the root is `null`, the tree is symmetric.\n2. Define a helper function that:\n   - Compares the values of two nodes.\n   - Recursively checks the left subtree of the first node with the right subtree of the second, and vice versa.\n3. Return `true` if all checks pass.\n\n#### Iterative :\n1. Use a queue to store node pairs for comparison.\n2. While the queue is not empty:\n   - Remove a pair from the queue.\n   - Check if both nodes are `null`. If yes, continue.\n   - If only one is `null`, return `false`.\n   - Check if their values are equal.\n   - Add their children to the queue in a mirrored order (left-right for one node and right-left for the other).\n\n---\n\n### **Complexity Analysis** :\n- **Time Complexity**: O(n), where n is the number of nodes in the tree. Each node is visited once.\n- **Space Complexity**:\n  - Recursive: O(h), where h is the height of the tree (call stack).\n  - Iterative: O(n), for the queue in the worst case.\n\n---\n\n### **Code Implementation**\n\n#### **C++**\n```cpp\nclass Solution {\npublic:\n    bool isSymmetric(TreeNode* root) {\n        if (!root) return true;\n        return isMirror(root->left, root->right);\n    }\n\n    bool isMirror(TreeNode* t1, TreeNode* t2) {\n        if (!t1 && !t2) return true;\n        if (!t1 || !t2) return false;\n        return (t1->val == t2->val) &&\n               isMirror(t1->left, t2->right) &&\n               isMirror(t1->right, t2->left);\n    }\n};\n```\n\n**Iterative Approach** :\n```cpp\nclass Solution {\npublic:\n    bool isSymmetric(TreeNode* root) {\n        if (!root) return true;\n        queue<TreeNode*> q;\n        q.push(root->left);\n        q.push(root->right);\n        while (!q.empty()) {\n            TreeNode* t1 = q.front(); q.pop();\n            TreeNode* t2 = q.front(); q.pop();\n            if (!t1 && !t2) continue;\n            if (!t1 || !t2 || t1->val != t2->val) return false;\n            q.push(t1->left);\n            q.push(t2->right);\n            q.push(t1->right);\n            q.push(t2->left);\n        }\n        return true;\n    }\n};\n```\n\n---\n\n#### **Java** :\n```java\nclass Solution {\n    public boolean isSymmetric(TreeNode root) {\n        if (root == null) return true;\n        return isMirror(root.left, root.right);\n    }\n\n    private boolean isMirror(TreeNode t1, TreeNode t2) {\n        if (t1 == null && t2 == null) return true;\n        if (t1 == null || t2 == null) return false;\n        return (t1.val == t2.val) &&\n               isMirror(t1.left, t2.right) &&\n               isMirror(t1.right, t2.left);\n    }\n}\n```\n\n**Iterative Approach** :\n```java\nclass Solution {\n    public boolean isSymmetric(TreeNode root) {\n        if (root == null) return true;\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.add(root.left);\n        queue.add(root.right);\n        while (!queue.isEmpty()) {\n            TreeNode t1 = queue.poll();\n            TreeNode t2 = queue.poll();\n            if (t1 == null && t2 == null) continue;\n            if (t1 == null || t2 == null || t1.val != t2.val) return false;\n            queue.add(t1.left);\n            queue.add(t2.right);\n            queue.add(t1.right);\n            queue.add(t2.left);\n        }\n        return true;\n    }\n}\n```\n\n---\n\n#### **Python 3** :\n```python\nclass Solution:\n    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n        if not root:\n            return True\n        return self.isMirror(root.left, root.right)\n\n    def isMirror(self, t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:\n        if not t1 and not t2:\n            return True\n        if not t1 or not t2:\n            return False\n        return (t1.val == t2.val and\n                self.isMirror(t1.left, t2.right) and\n                self.isMirror(t1.right, t2.left))\n```\n\n**Iterative Approach**\n```python\nfrom collections import deque\n\nclass Solution:\n    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n        if not root:\n            return True\n        queue = deque([root.left, root.right])\n        while queue:\n            t1 = queue.popleft()\n            t2 = queue.popleft()\n            if not t1 and not t2:\n                continue\n            if not t1 or not t2 or t1.val != t2.val:\n                return False\n            queue.append(t1.left)\n            queue.append(t2.right)\n            queue.append(t1.right)\n            queue.append(t2.left)\n        return True\n```\n\n---\n\n### **Example Walkthrough** :\n\n#### Example 1:\n- **Input**: `[1, 2, 2, 3, 4, 4, 3]`\n- **Execution**:\n  - Compare `2` and `2`: Equal.\n  - Compare `3` and `3`: Equal.\n  - Compare `4` and `4`: Equal.\n- **Output**: `true`.\n\n#### Example 2:\n- **Input**: `[1, 2, 2, null, 3, null, 3]`\n- **Execution**:\n  - Compare `2` and `2`: Equal.\n  - Compare `null` and `3`: Not equal.\n- **Output**: `false`.\n\n---\n\n### **Edge Cases** :\n1. **Empty Tree**: `root = null` \u2192 Symmetric (`true`).\n2. **Single Node**: `root = [1]` \u2192 Symmetric (`true`).\n3. **Unbalanced Tree**: `root = [1, 2, 2, 3, null, null, 3]` \u2192 Not symmetric (`false`).\n\n![image.png](https://assets.leetcode.com/users/images/a3e89fc7-bde6-4538-a83e-f08130ec2cdd_1732763353.596884.png)\n
['Tree', 'Depth-First Search', 'C++', 'Java', 'Python3']