[Python] Intuitive recursive solution, O(h), explained
This is exercise to undertand what is Binary Search Tree and how it works. Remember, that left subtree is always lesser than root and right subtree is always bi
This is exercise to undertand what is Binary Search Tree and how it works. Remember, that **left** subtree is always lesser than root and **right** subtree is always bigger than root.\nSo, what we need to do? We start from the root of our tree and compare value in its root. If value we are looking is **less** than value in root, we go left, if it is **more**, we go to the right. When we stop? Either if we found place, where these two values are equal, or we reached NULL leaf (it means we visited leaf and descended to its NULL children). In this cases we save found node to global variable, which we return in the end.\n\n**Complexity**, both time and space is `O(h)`, where `h` is heigth of our tree.\n\n**Remark**: I used `helper` function, which is not necessary here, but in this way the code is more universal for different trees traversal problems, where you need to return more difficult objects. \n\n```\nclass Solution:\n    def helper(self, root):\n        if not root or root.val == self.val: \n            self.Found = root\n            return root\n        \n        if root.val < self.val:\n            return self.helper(root.right)\n        \n        if root.val > self.val:\n            return self.helper(root.left)\n    \n    def searchBST(self, root, val):\n        self.val = val\n        self.Found = None\n        self.helper(root)\n        return self.Found\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Recursion']