Search in BST Solution

The recursive solution is clean:

def searchBST(root, val):
    if root == null or root.val == val:
        return root
    if val < root.val:
        return searchBST(root.left, val)
    return searchBST(root.right, val)

The iterative solution uses constant space:

def searchBST(root, val):
    while root and root.val != val:
        root = root.left if val < root.val else root.right
    return root

Time: $O(h)$. Space: $O(1)$ iterative, $O(h)$ recursive.

This problem is foundational. Make sure you can write it quickly without thinking.