Binary Search Tree Search

Binary Search Tree (BST) search locates a key by following the tree structure and using the ordering invariant:

• all keys in the left subtree are smaller
• all keys in the right subtree are larger

This property allows you to discard half of the remaining subtree at each step, similar in spirit to binary search on arrays.

Problem

Given a binary search tree with root node root and a target key x, find a node such that

If no such node exists, return null.

Algorithm

Start at the root. At each node:

• if the current key equals the target, return it
• if the target is smaller, move to the left child
• if the target is larger, move to the right child

Continue until you either find the key or reach a null pointer.

bst_search(root, x):
    node = root
    while node != null:
        if x == node.key:
            return node
        else if x < node.key:
            node = node.left
        else:
            node = node.right
    return null

Example

Consider the tree:

        8
       / \
      3   10
     / \    \
    1   6    14

Search for 6:

Correctness

The BST invariant ensures that at any node:

• all possible matches for $x$ must lie entirely in one subtree
• the algorithm always moves into the only subtree that can contain $x$

If the algorithm reaches a null pointer, then no valid position for $x$ exists in the tree.

Complexity

Space complexity:

• iterative version: $O(1)$
• recursive version: $O(h)$ where $h$ is tree height

When to Use

BST search is useful when:

• you need dynamic ordered data
• insert, delete, and search operations must all be supported
• you want in-order traversal to produce sorted output

For guaranteed logarithmic performance, use balanced variants such as AVL trees or red-black trees.

Implementation

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def bst_search(root, x):
    node = root
    while node:
        if x == node.key:
            return node
        elif x < node.key:
            node = node.left
        else:
            node = node.right
    return None

type Node struct {
	Key   int
	Left  *Node
	Right *Node
}

func BSTSearch(root *Node, x int) *Node {
	node := root
	for node != nil {
		if x == node.Key {
			return node
		} else if x < node.Key {
			node = node.Left
		} else {
			node = node.Right
		}
	}
	return nil
}