✔️ Python3 || Simple 3 lines
Trees can be traversed using either one of the following approaches:\n1. Inorder\n2. Preorder\n3. Postorder \n4. BFS\n5. DFS\n\nBut for the given problem, we ar
Trees can be traversed using either one of the following approaches:\n1. Inorder\n2. Preorder\n3. Postorder \n4. BFS\n5. DFS\n\nBut for the given problem, we are using **B**inary **S**earch **T**ree and BST has an important property which we can rely on to reduce the overall time for traversal:\n**`Each node in the tree has a key which is greater than all the keys in the left subtree and smaller than those in the right subtree`**\n\n\n**The recursive solution:** \n```\nclass Solution:\n    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n        if not root or root.val == val:\n            return root        \n        return self.searchBST(root.left, val) if val < root.val else self.searchBST(root.right, val)\n```\n**Time Complexity** : **O(h)** where **h** is height of the tree. The **h** can be either **logN**  if its balanced tree or **N** if its a skewed tree.\n**Space Complexity**: **O(h)** where **h** is height of the tree. The **h** can be either **logN**  if its balanced tree or **N** if its a skewed tree.\n\nI usually don\'t like to write a recursive solution in languages which doesn\'t support tail recursion optimization. As I usually prefer Python for my solutions, I came up with an iterative solution:\n\n```\nclass Solution:\n    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:\n        while root and root.val != val:\n            root = root.left if val < root.val else root.right\n        return root\n```\n\n**Time Complexity** : **O(h)** where **h** is height of the tree. The **h** can be either **logN**  if its balanced tree or **N** if its a skewed tree.\n**Space Complexity**: **O(1)**\n____________________________________________________________________________________________________________\n***Please upvote if you find it useful***
['Python', 'Python3']