Binary Search Trees

The BST Property

A binary search tree (BST) is a rooted binary tree where each node stores a (key, value) pair and satisfies the binary search tree property: for any node with key k, all keys in its left subtree are strictly less than k, and all keys in its right subtree are strictly greater than k. Duplicate keys are not permitted in search trees.

This property enables efficient search: at each node, compare the target key with the node’s key and descend left or right accordingly.

Operations

All BST operations traverse a path from the root to a leaf, so each runs in $\Theta(h)$ time where $h$ is the height of the tree.

Search

Start at the root. If the current node’s key equals the target, return it. Otherwise, go left if the target is smaller, right if larger. If a NIL pointer is reached, the key is not present.

Insert

Search for the key. If found, update the payload (replace the value). If not found, the search terminates at a NIL child pointer of some node; create a new node there.

Delete

Three cases for the node d containing the key to delete:

1. No children: Remove d from its parent (set the parent’s pointer to NIL).
2. One child: Replace d with its child in the parent’s pointer.
3. Two children: Find d’s inorder successor (or predecessor), which has at most one child. Copy the successor’s (key, value) into d, then delete the successor node.

Min, Max, Predecessor, Successor

• Minimum: follow left pointers until NIL; the last non-NIL node.
• Maximum: follow right pointers until NIL.
• Successor: if node has a right child, find the minimum of the right subtree. Otherwise, walk up until a “first up-right” is found (the first ancestor for which the node is in the left subtree).
• Predecessor: symmetric, using left subtree maximum or “first up-left”.

Predecessor and successor require parent pointers; minimum and maximum do not.

Inorder Traversal

An inorder traversal (left subtree, node, right subtree) visits nodes in sorted key order. This is a $\Theta(n)$ operation that produces the sorted sequence of all keys.

Example: Building a BST

Insert keys [N, D, A, I, S, O, R, U] in order:

Step 1: [N]
Step 2: [N] with left child [D]
Step 3: [N] with [D] having left child [A]
...
Result:       N
           /     \
         D        S
       /   \    /   \
      A     I  O     U
             \
              R

The Degeneracy Problem

If keys are inserted in sorted order (e.g. A, D, I, N, O, R, S, U), each new key is larger than all existing keys, so each insert goes to the rightmost position. The tree becomes a linked list: every node has at most one child, and height $h = n$.

In this worst case, all operations become $\Theta(n)$. The average case for random insertion order gives $h = \Theta(\log n)$, but adversarial or sorted input breaks this.

This motivates self-balancing BST variants (red-black trees, AVL trees) that guarantee $O(\log n)$ height regardless of insertion order.

Summary

Operation	Time	Notes
Search	$\Theta(h)$	Follow path from root
Insert	$\Theta(h)$	Add as leaf
Delete	$\Theta(h)$	Three cases
Min/Max	$\Theta(h)$	Follow left/right pointers
Predecessor/Successor	$\Theta(h)$	Requires parent pointers
Inorder traversal	$\Theta(n)$	Sorted order
Best height	$\Theta(\log n)$	Balanced
Worst height	$\Theta(n)$	Degenerate (sorted input)