【Video】Going to left side and right side at the same time
Intuition\nGoing to left side and right side at the same time\n\n# Solution Video\n\nhttps://youtu.be/ywAZyIjRmoo\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget 
# Intuition\nGoing to left side and right side at the same time\n\n# Solution Video\n\nhttps://youtu.be/ywAZyIjRmoo\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 11,448\nThank you for your support!\n\n---\n\n# Approach\n\nWe are going to left side and right side at the same time.\n\nWe have two base cases.\n\n---\n\n\u25FD\uFE0F Base Cases\n\nIf both sides are null at the same time, return `True` because we reach the end of a tree.\n\nIf one of sides is null, return `False` because it\'s not symmetric.\n\n---\n\n##### How we move to left side and right side?\n\nLook at the tree below. This is a `True` case.\n\n```\n        1\n       / \\\n      2   2\n       \\ / \n       3 3\n```\n\nEvery time we have to compare two nodes from both sides.\n\n---\n\n\u2B50\uFE0F Points\n\nIf we go left on the left side, we should go right on the right side.(= node `2` case).\n\nIf we go right on the left side, we should go left on the right side.(= node `3` case).\n\n---\n\n**Because `True` case of the tree is like mirror from center line.**\n```\n        1\n       /|\\\n      2 | 2\n       \\|/ \n       3|3\n```\n\nEasy!\uD83D\uDE04\nLet\'s see solution codes!\n\n---\n\nhttps://youtu.be/bU_dXCOWHls\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(h)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n```python []\nclass Solution:\n    def isSymmetric(self, root: Optional[TreeNode]) -> bool:\n        \n        def is_mirror(n1, n2): # n1:left, n2:right\n            if not n1 and not n2:\n                return True\n            \n            if not n1 or not n2:\n                return False\n            \n            return n1.val == n2.val and is_mirror(n1.left, n2.right) and is_mirror(n1.right, n2.left)\n        \n        return is_mirror(root.left, root.right)\n```\n```javascript []\nvar isSymmetric = function(root) {\n    const isMirror = (n1, n2) => {\n        if (!n1 && !n2) {\n            return true;\n        }\n        \n        if (!n1 || !n2) {\n            return false;\n        }\n        \n        return n1.val === n2.val && isMirror(n1.left, n2.right) && isMirror(n1.right, n2.left);\n    };\n    \n    return isMirror(root.left, root.right);\n};\n```\n```java []\nclass Solution {\n    public boolean isSymmetric(TreeNode root) {\n        return isMirror(root.left, root.right);\n    }\n    \n    private boolean isMirror(TreeNode n1, TreeNode n2) {\n        if (n1 == null && n2 == null) {\n            return true;\n        }\n        \n        if (n1 == null || n2 == null) {\n            return false;\n        }\n        \n        return n1.val == n2.val && isMirror(n1.left, n2.right) && isMirror(n1.right, n2.left);\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    bool isSymmetric(TreeNode* root) {\n        return isMirror(root->left, root->right);\n    }\n\nprivate:\n    bool isMirror(TreeNode* n1, TreeNode* n2) {\n        if (n1 == nullptr && n2 == nullptr) {\n            return true;\n        }\n        \n        if (n1 == nullptr || n2 == nullptr) {\n            return false;\n        }\n        \n        return n1->val == n2->val && isMirror(n1->left, n2->right) && isMirror(n1->right, n2->left);\n    }\n};\n```\n\n# Step by Step Algorithm\n\n##### 1. **Helper Function `is_mirror` Definition**\n```python\ndef is_mirror(n1, n2): # n1:left, n2:right\n```\n- **Explanation**: `is_mirror` is a nested helper function that checks if two subtrees (`n1` and `n2`) are mirror images of each other. This function will be called recursively to compare corresponding nodes in the left and right subtrees of the tree.\n\n##### 2. **Base Case: Both Nodes Are `None`**\n```python\nif not n1 and not n2:\n    return True\n```\n- **Explanation**: If both `n1` and `n2` are `None`, it means that both corresponding nodes in the left and right subtrees are absent. Since an empty subtree is symmetric to another empty subtree, this part of the code returns `True`.\n\n##### 3. **Base Case: One Node Is `None` and the Other Is Not**\n```python\nif not n1 or not n2:\n    return False\n```\n- **Explanation**: If one of the nodes (`n1` or `n2`) is `None` while the other is not, it means that the structure of the two subtrees is different, and therefore they cannot be mirror images of each other. This part of the code returns `False`.\n\n##### 4. **Recursive Case: Compare Values and Subtrees**\n```python\nreturn n1.val == n2.val and is_mirror(n1.left, n2.right) and is_mirror(n1.right, n2.left)\n```\n- **Explanation**: This line checks three conditions:\n  1. The values of `n1` and `n2` should be the same (`n1.val == n2.val`).\n  2. The left subtree of `n1` should be a mirror image of the right subtree of `n2` (`is_mirror(n1.left, n2.right)`).\n  3. The right subtree of `n1` should be a mirror image of the left subtree of `n2` (`is_mirror(n1.right, n2.left)`).\n  \n  If all three conditions are `True`, the function returns `True`, indicating that the subtrees rooted at `n1` and `n2` are mirror images of each other.\n\n##### 5. **Initial Call to `is_mirror`**\n```python\nreturn is_mirror(root.left, root.right)\n```\n- **Explanation**: The `isSymmetric` method calls the `is_mirror` function with the left and right children of the root node (`root.left` and `root.right`). This initiates the recursive process of checking whether the left and right subtrees of the root are mirror images of each other.\n\n##### 6. **Return the Result**\n- **Explanation**: The final result of the `is_mirror` function call determines whether the tree is symmetric. If the left and right subtrees of the root are mirror images, the function returns `True`; otherwise, it returns `False`.\n\n---\n\nThank you for reading my post. Please upvote it and don\'t forget to subscribe to my channel!\n\n### \u2B50\uFE0F Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n### \u2B50\uFE0F Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n### \u2B50\uFE0F Related Video\n\n#100 Same Tree\n\nhttps://youtu.be/tRFQ7p0ucUw\n
['Tree', 'Depth-First Search', 'Binary Tree', 'C++', 'Java', 'Python3', 'JavaScript']