BST Search

Search follows the BST property directly:

def search(root, target):
    if root == null:
        return null
    if target == root.val:
        return root
    if target < root.val:
        return search(root.left, target)
    else:
        return search(root.right, target)

Iterative version:

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

Time: $O(h)$ where $h$ is tree height.

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

In a balanced tree, $h = O(\log n)$. In the worst case (skewed), $h = O(n)$.