Day 72 || With Diagram || Iterative and Recursive || Easiest Beginner Friendly Sol
NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.\n\n# Intuitio
**NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Intuition of this Problem:\nWe need to validate only 3 conditions including base condition and recursively call to the function:\n- If both "leftRoot" and "rightRoot" are null, return true\n- If only one of "leftRoot" or "rightRoot" is null, return false\n- If "leftRoot" and "rightRoot" are not null and their values are not equal, return false\n- If "leftRoot" and "rightRoot" are not null and their values are equal, recursively call "isTreeSymmetric" on the left child of "leftRoot" and the right child of "rightRoot", and the right child of "leftRoot" and the left child of "rightRoot"\n\n![WhatsApp Image 2023-01-24 at 6.54.24 PM.jpeg](https://assets.leetcode.com/users/images/3ce67a24-c51f-4cff-a5ac-58425726b650_1674566690.8242106.jpeg)\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach for this Problem:\n1. Define a function "isTreeSymmetric" that takes in two TreeNode pointers as inputs, "leftRoot" and "rightRoot"\n2. If both "leftRoot" and "rightRoot" are null, return true\n3. If only one of "leftRoot" or "rightRoot" is null, return false\n4. If "leftRoot" and "rightRoot" are not null and their values are not equal, return false\n5. If "leftRoot" and "rightRoot" are not null and their values are equal, recursively call "isTreeSymmetric" on the left child of "leftRoot" and the right child of "rightRoot", and the right child of "leftRoot" and the left child of "rightRoot"\n6. Return true if both recursive calls return true, else return false\n7. Define a function "isSymmetric" that takes in a TreeNode pointer "root" as input\n8. Call "isTreeSymmetric" on the left child of "root" and the right child of "root" and return the result\n<!-- Describe your approach to solving the problem. -->\n\n# Humble Request:\n- If my solution is helpful to you then please **UPVOTE** my solution, your **UPVOTE** motivates me to post such kind of solution.\n- Please let me know in comments if there is need to do any improvement in my approach, code....anything.\n- **Let\'s connect on** https://www.linkedin.com/in/abhinash-singh-1b851b188\n\n![57jfh9.jpg](https://assets.leetcode.com/users/images/c2826b72-fb1c-464c-9f95-d9e578abcaf3_1674104075.4732099.jpeg)\n\n# Code:\n```C++ []\n//Iterative approach\n// TC - O(n), where n is the number of nodes in the binary tree. This is because the code visits each node in the binary tree once, and the while loop iterates over all nodes in the worst-case scenario.\n// SC - O(n), where n is the number of nodes in the binary tree. This is because the code uses a queue to store nodes in a level-by-level manner, and in the worst-case scenario, the queue will contain all the nodes of the binary tree. Therefore, the space required by the queue will be proportional to the number of nodes in the tree, leading to O(n) space complexity.\nclass Solution {\npublic:\n    bool isSymmetric(TreeNode* root) {\n        if (root == nullptr)\n            return true;\n        queue<TreeNode*> q;\n        q.push(root -> left);\n        q.push(root -> right);\n        while (!q.empty()) {\n            TreeNode *leftRoot = q.front();\n            q.pop();\n            TreeNode *rightRoot = q.front();\n            q.pop();\n            if (leftRoot == nullptr && rightRoot == nullptr)\n                continue;\n            if ((leftRoot == nullptr && rightRoot != nullptr) || (leftRoot != nullptr && rightRoot == nullptr))\n                return false;\n            if (leftRoot -> val != rightRoot -> val)\n                return false;\n            q.push(leftRoot -> left);\n            q.push(rightRoot -> right);\n            q.push(leftRoot -> right);\n            q.push(rightRoot -> left);\n        }\n        return true;\n    }\n};\n```\n```C++ []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    bool isTreeSymmetric(TreeNode* leftRoot, TreeNode* rightRoot){\n        if(leftRoot == nullptr && rightRoot == nullptr)\n            return true;\n        if((leftRoot == nullptr && rightRoot != nullptr)  || (leftRoot != nullptr && rightRoot == nullptr))\n            return false;\n        if(leftRoot -> val != rightRoot -> val)\n            return false;\n        return isTreeSymmetric(leftRoot -> left, rightRoot -> right) && isTreeSymmetric(leftRoot -> right, rightRoot -> left);\n    }\n    bool isSymmetric(TreeNode* root) {\n        return isTreeSymmetric(root -> left, root -> right);\n    }\n};\n```\n```Java []\nclass Solution {\n    public boolean isTreeSymmetric(TreeNode leftRoot, TreeNode rightRoot){\n        if(leftRoot == null && rightRoot == null)\n            return true;\n        if((leftRoot == null && rightRoot != null)  || (leftRoot != null && rightRoot == null))\n            return false;\n        if(leftRoot.val != rightRoot.val)\n            return false;\n        return isTreeSymmetric(leftRoot.left, rightRoot.right) && isTreeSymmetric(leftRoot.right, rightRoot.left);\n    }\n    public boolean isSymmetric(TreeNode root) {\n        return isTreeSymmetric(root.left, root.right);\n    }\n}\n```\n```Python []\nclass Solution:\n    def isTreeSymmetric(self, leftRoot, rightRoot):\n        if leftRoot is None and rightRoot is None:\n            return True\n        if (leftRoot is None and rightRoot is not None) or (leftRoot is not None and rightRoot is None):\n            return False\n        if leftRoot.val != rightRoot.val:\n            return False\n        return self.isTreeSymmetric(leftRoot.left, rightRoot.right) and self.isTreeSymmetric(leftRoot.right, rightRoot.left)\n    def isSymmetric(self, root):\n        return self.isTreeSymmetric(root.left, root.right)\n```\n\n# Time Complexity and Space Complexity:\n- Time complexity: **O(n)**, where n is the total number of nodes in the binary tree. This is because the solution visits each node once and compares its values with the corresponding symmetric node, thus the function isTreeSymmetric() is called on each node at most once. The time complexity of the isTreeSymmetric() function is O(n/2) because it only visits half of the nodes (in the best case when the tree is symmetric) and in the worst case it visits all nodes in the tree (when the tree is not symmetric).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(h)**, where h is the height of the binary tree. This is because the recursive calls made by the solution consume memory on the call stack equal to the height of the tree. In the worst case when the binary tree is linear, the height of the tree is equal to n, thus the space complexity becomes O(n). However, in the best case when the binary tree is perfectly balanced, the height of the tree is log(n), thus the space complexity becomes O(log(n)).\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Depth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3']