C++ recursive solution|Easy Observation|Day 13-SUCCESSFULL|#LEETCODEDAILY
Intuition\n Describe your first thoughts on how to solve this problem. \nOn observing we clearly see we have to perform repetitive task for two roots which are 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nOn observing we clearly see we have to perform repetitive task for two roots which are mainly the left and right part we want to compare \nSo we can divide our bigger problem into smaller problem of taking the whole tree and only compare the left and right part of the root  which hints us towards recursion.\n\n![subtrees.png](https://assets.leetcode.com/users/images/a72ac51c-afe5-4eee-982b-a88e3050788e_1678681623.2849514.png)\n\n \n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can observe that a binary tree is symmetric if the following conditions are met:\n\n- The value of the left subtree\'s root node is equal to the value of the right subtree\'s root node.\n- The left subtree\'s left child is identical to the right subtree\'s right child.\n- The left subtree\'s right child is identical to the right subtree\'s left child.\n- Both the left and right subtrees are either empty (NULL) or non-empty.\nIt is important to note that if only one of the left and right subtrees is non-empty, we cannot compare further as the identical part of the subtree is missing. Therefore, both subtrees must be either empty or non-empty in a symmetric binary tree.\n\n# Complexity\n- ## Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n**O(n)**, where n is the total number of nodes in the binary tree.  The time complexity of the symmetric() 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) in this case it is 0(N)**.\n\n\n- ## Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n**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\nFeel free to share any improvements that can be done to the code \n# If u wish to connect with me [LinkedIn](https://www.linkedin.com/in/pawas-goyal/)\n\n\n# Code\n```\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 symmetric(TreeNode *lst,TreeNode *rst){\n        if(lst==NULL && rst==NULL)return true;\n        if(lst==NULL || rst==NULL)return false;\n        if(lst->val!=rst->val)return false;\n        return symmetric(lst->left,rst->right)&&symmetric(lst->right,rst->left);\n        \n    }\n    bool isSymmetric(TreeNode* root) {\n        if(!root || root->right==NULL && root->left==NULL)return true;\n        return symmetric(root->left,root->right);\n        \n    }\n};\n```\n![06351dc5-1e55-461d-acf2-60c9048c4726_1675165944.4721575.webp](https://assets.leetcode.com/users/images/6c305529-29d2-4a58-b09d-ee292769d403_1678682609.1504712.webp)\n\n# UPVOTE IF U LIKE THE SOLUTION\n\n
['C++']