【Video】Visualized Solution
Intuition\nThis is typical binary search tree problem.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/kPcYYCbUUEA\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget 
# Intuition\nThis is typical binary search tree problem.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/kPcYYCbUUEA\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: 6,285\nThank you for your support!\n\n---\n\n# Approach\n\nTypical Binary Search Tree has rules as follow:\n\n\n---\n\n\u2B50\uFE0F Points\n\n- All values of left side of current root are less than the root value.\n- All values of right side of current root are greater than the root value.\n\n---\n\nLet\'s solve this qustion with the example below.\n```\n       7\n     /   \\\n    5    10\n   / \\   / \\\n  2   6 8  15\n            / \\\n           12 20\n\nval = 15\n```\nWe are now at `7`.We have two choices. **Go left or right with the rule above**.\n\nIn this case, we should go right because \n\n```\n15 > 7\n```\nNow we are at 10. Again we have two choices.\n```\n15 > 10\n```\nNow we find the same value, so return current node.\n\nEasy!\uD83D\uDE03\nLet\'s see solution codes!\n\n\n---\n\nhttps://youtu.be/bU_dXCOWHls\n\n---\n\n\n\n# Complexity\n- Time complexity:\n\n    - In the worst case, the height $$(h)$$ could be as large as $$(n)$$(the number of nodes) if the tree is unbalanced, leading to $$O(n)$$complexity.\n    - In the best case, if the tree is balanced, the height $$(h)$$ would be $$(log n)$$, leading to $$O(log n)$$ complexity.\n\n- Space complexity:\n\n    - In the worst case, the space complexity is $$O(n)$$ if the tree is completely unbalanced.\n    - In the best case, the space complexity is $$O(log n)$$ if the tree is balanced.\n\n\n```python []\nclass Solution:\n    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n        if not root:\n            return None\n        \n        if root.val == val:\n            return root\n        elif root.val > val:\n            return self.searchBST(root.left, val)\n        else:\n            return self.searchBST(root.right, val)\n```\n```javascript []\nvar searchBST = function(root, val) {\n    if (!root) {\n        return null;\n    }\n    if (root.val === val) {\n        return root;\n    } else if (root.val > val) {\n        return searchBST(root.left, val);\n    } else {\n        return searchBST(root.right, val);\n    }\n};\n```\n```java []\nclass Solution {\n    public TreeNode searchBST(TreeNode root, int val) {\n        if (root == null) {\n            return null;\n        }\n        if (root.val == val) {\n            return root;\n        } else if (root.val > val) {\n            return searchBST(root.left, val);\n        } else {\n            return searchBST(root.right, val);\n        }        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    TreeNode* searchBST(TreeNode* root, int val) {\n        if (!root) {\n            return nullptr;\n        }\n        if (root->val == val) {\n            return root;\n        } else if (root->val > val) {\n            return searchBST(root->left, val);\n        } else {\n            return searchBST(root->right, val);\n        }        \n    }\n};\n```\n\n**1. Base Case:**\n\n   - If the `root` node is `None`, the search is complete, and the target value is not found. Return `None`.\n\n**2. Search for Value:**\n\n   - Compare the target value (`val`) with the current node\'s value (`root.val`).\n   - If `val == root.val`, the search is successful. Return `root` as the node containing the target value.\n\n**3. Recursive Search (Left or Right Subtree):**\n\n   - If `val < root.val`:\n     - The target value is smaller than the current node, so it must be in the left subtree (remember BST property).\n     - Recursively call the same logic (steps 2-4) on the `root.left` subtree, passing the same `val` to search for.\n   - If `val > root.val`:\n     - The target value is larger than the current node, so it must be in the right subtree (remember BST property).\n     - Recursively call the same logic (steps 2-4) on the `root.right` subtree, passing the same `val` to search for.\n\n**4. Recursive Result Handling:**\n\n   - The result of the recursive call (either `None` if not found or the node containing the value) is returned by the current step.\n\n**Overall Process:**\n\nThe algorithm starts at the root node and repeatedly compares the target value with the current node\'s value. Based on the comparison, it either returns the node if the value is found, or it recursively searches the appropriate subtree until the target is found or an empty subtree (resulting in `None`) is reached. This recursive approach efficiently utilizes the BST property of ordered values in each subtree.\n\n\n---\n\nThank you for reading my post.\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 My previous video - Generate Parentheses #22\n\nhttps://youtu.be/FMoH-huqTe4\n
['C++', 'Java', 'Python3', 'JavaScript']