Recursive Approach with Easy Steps
Please Upvote my solution, if you find it helpful ;)\n\n# Intuition\nImagine you have a tree where each node has a value, and the nodes are arranged in a specif
## ***Please Upvote my solution, if you find it helpful ;)***\n\n# Intuition\nImagine you have a tree where each node has a value, and the nodes are arranged in a specific order, called a binary search tree (BST). The BST has a special property: for any node, all the nodes in its left subtree have values smaller than the node\'s value, and all the nodes in its right subtree have values greater than the node\'s value. We need to find a specific value (val) in this tree and return the subtree that contains the value.\n\n# Approach\nTo find the value in the binary search tree, we use a recursive approach:\n\n1. We start at the root of the tree and check if it\'s null or if its value is equal to the target value val. If so, we have found the node with the value we want, and we return it.\n\n1. If the target value val is smaller than the root\'s value, we know the node we want must be in the left subtree. So, we repeat the search process on the left subtree by calling the method again with the left subtree as the new root.\n\n1. If the target value val is greater than the root\'s value, we know the node we want must be in the right subtree. So, we repeat the search process on the right subtree by calling the method again with the right subtree as the new root.\n\n1. We continue this process recursively until we find the node with the target value or reach a dead-end (a leaf node) in the tree. If we reach a dead-end and still haven\'t found the value, we return null to indicate that the value is not present in the tree.\n\n\n# Complexity\n- Time complexity:\nThe time it takes to find the value in the binary search tree depends on the height of the tree. In the best case (a balanced tree), the height is relatively small, and the search is quick, taking logarithmic time (O(log n)), where n is the number of nodes in the tree. However, in the worst case (a skewed tree), the height can be equal to the number of nodes, resulting in a linear search that takes O(n) time.\n\n\n- Space complexity:\nThe space required by the recursive approach depends on the height of the tree as well. For each recursive call, some space is used to keep track of the current node and the next nodes to explore. In the best and average cases (balanced tree), the space complexity is O(log n). In the worst case (skewed tree), the space complexity is O(n).\n\n# Code\n```java []\nclass Solution {\n    public TreeNode searchBST(TreeNode root, int val) {\n        // If the root is null or its value is equal to the target value, return the root\n        if (root == null || root.val == val) {\n            return root;\n        }\n        \n        // If the target value is less than the root\'s value, search in the left subtree\n        if (val < root.val) {\n            return searchBST(root.left, val);\n        } else {\n            // If the target value is greater than the root\'s value, search in the right subtree\n            return searchBST(root.right, val);\n        }\n    }\n}\n\n```\n```python []\nclass Solution(object):\n    def searchBST(self, root, val):\n        # If the root is None or its value is equal to the target value, return the root\n        if not root or root.val == val:\n            return root\n        \n        # If the target value is less than the root\'s value, search in the left subtree\n        if val < root.val:\n            return self.searchBST(root.left, val)\n        else:\n            # If the target value is greater than the root\'s value, search in the right subtree\n            return self.searchBST(root.right, val)\n```\n```C++ []\nclass Solution {\npublic:\n    TreeNode* searchBST(TreeNode* root, int val) {\n        // If the root is NULL or its value is equal to the target value, return the root\n        if (!root || root->val == val) {\n            return root;\n        }\n\n        // If the target value is less than the root\'s value, search in the left subtree\n        if (val < root->val) {\n            return searchBST(root->left, val);\n        } else {\n            // If the target value is greater than the root\'s value, search in the right subtree\n            return searchBST(root->right, val);\n        }\n    }\n};\n```\n## ***Please Upvote my solution, if you find it helpful ;)***\n![6a87bc25-d70b-424f-9e60-7da6f345b82a_1673875931.8933976.jpeg](https://assets.leetcode.com/users/images/58e314db-5e8d-4d23-9d0f-4f6f35e25002_1689872832.2468483.jpeg)\n\n
['Binary Search Tree', 'Binary Tree', 'Python', 'C++', 'Java']