BST Search — Finding a Value in a Binary Search Tree

BST Search Algorithm

Searching in a Binary Search Tree leverages the ordering property: at each node, if the target is smaller go left, if larger go right, if equal you have found it. This binary decision at each level is what gives BSTs their O(log n) average search time.

Algorithm

SEARCH(node, target):
  if node is NULL: return NOT_FOUND
  if target == node.value: return FOUND
  if target < node.value: return SEARCH(node.left, target)
  return SEARCH(node.right, target)

Step-by-Step Example

Searching for 6 in this BST:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \
      4   7

Path: 8 → 3 → 6 (found!)
Steps: 6 < 8 (go left) → 6 > 3 (go right) → 6 == 6 (found)

Searching for a Missing Value

Searching for 5:

Path: 8 → 3 → 6 → 4 → NULL (not found)

When the search reaches a null pointer, the value does not exist in the tree.

Time Complexity

Case	Complexity	When
Best	O(1)	Target is the root
Average	O(log n)	Tree is reasonably balanced
Worst	O(n)	Tree is completely skewed

Iterative Version

SEARCH_ITERATIVE(root, target):
  current = root
  while current != NULL:
    if target == current.value: return FOUND
    if target < current.value:
      current = current.left
    else:
      current = current.right
  return NOT_FOUND

The iterative version uses O(1) space since it does not use the call stack, while the recursive version uses O(h) space for the recursion stack.

Comparison with Linear Search

In an unsorted array, searching for a value requires scanning every element — O(n) in the worst case. A balanced BST reduces this to O(log n), which for 1 million elements means ~20 comparisons instead of 1,000,000.