Binary Search Trees: Querying, Inserting, and Deleting Efficiently

The Binary-Search-Tree Property

A Binary Search Tree (BST) is organized using the same binary tree node structure introduced earlier in this series, but with a crucial ordering constraint called the Binary-Search-Tree Property: for any node x, every key in x's left subtree is less than or equal to x's key, and every key in x's right subtree is greater than or equal to x's key.

Example valid BST:
              8
            /   \
           3     10
          / \      \
         1   6      14
            / \     /
           4   7   13

Verify: every left descendant is ≤ its ancestor,
every right descendant is ≥ its ancestor

This ordering property is what makes efficient search possible: at every node, comparing the target key against the current node's key immediately determines which single subtree could possibly contain it, eliminating the other subtree from consideration entirely.

Querying a Binary Search Tree

Searching for a Key

TREE-SEARCH(x, k):
  if x == NIL or k == x.key:
      return x
  if k < x.key:
      return TREE-SEARCH(x.left, k)
  else:
      return TREE-SEARCH(x.right, k)

At each step, the search follows exactly one path from the root toward a leaf, comparing the target key and branching left or right accordingly. This means the running time is proportional to the length of the path followed, which is at most the tree's height h, giving a running time of O(h).

Finding the Minimum and Maximum

Because of the binary-search-tree property, the minimum element is always found by following left pointers as far as possible, and the maximum by following right pointers as far as possible.

TREE-MINIMUM(x):
  while x.left ≠ NIL:
      x = x.left
  return x

TREE-MAXIMUM(x):
  while x.right ≠ NIL:
      x = x.right
  return x

Both operations run in O(h) time, following a single path from the given node to a leaf.

Finding the Successor

The Successor of a node is the node with the smallest key greater than the given node's key — essentially, "the next element" if the tree were flattened into sorted order. Finding it requires two cases.

TREE-SUCCESSOR(x):
  if x.right ≠ NIL:
      return TREE-MINIMUM(x.right)
  y = x.p
  while y ≠ NIL and x == y.right:
      x = y
      y = y.p
  return y

If x has a right subtree, its successor is simply the minimum of that right subtree — the smallest value still greater than x. If x has no right subtree, the successor is found by walking up the tree until finding an ancestor that is a left child of its own parent — that parent is the successor. This operation also runs in O(h) time.

Inserting a New Key

Insertion follows the same comparison logic as search, walking down the tree until finding the correct empty position for the new node, then attaching it there as a leaf.

TREE-INSERT(T, z):
  y = NIL
  x = T.root
  while x ≠ NIL:
      y = x
      if z.key < x.key:
          x = x.left
      else:
          x = x.right
  z.p = y
  if y == NIL:
      T.root = z          // tree was empty
  elif z.key < y.key:
      y.left = z
  else:
      y.right = z

Since insertion simply walks a single path from root to leaf before attaching the new node, it runs in O(h) time, matching search and the other query operations.

Deleting a Key: The Most Intricate Operation

Deletion is more subtle than insertion because removing a node might disconnect its subtrees, and the tree's structure must be carefully repaired. There are three distinct cases to consider.

Case 1: The Node Has No Children

Simply remove the node by updating its parent to no longer point to it.

Case 2: The Node Has Exactly One Child

Splice the node out of the tree by connecting its parent directly to its single child, effectively promoting the child to take the deleted node's place.

Case 3: The Node Has Two Children

This case is the most involved. The node cannot simply be spliced out, since it has two subtrees that both need to remain connected somewhere. The standard solution finds the node's successor (which, as shown above, must have at most one child, since it is the minimum of the right subtree and therefore has no left child), and uses that successor to replace the deleted node's position.

To delete a node z with two children:
1. Find y = TREE-SUCCESSOR(z), which lies within z's right subtree
2. If y is not z's direct right child:
     first splice y out of its current position (Case 1 or 2 above),
     since y has at most one child (its right child)
     then put y in z's place, giving y both of z's children
3. If y IS z's direct right child:
     simply put y in z's place, keeping z's original left child
     (y already correctly retains its own right subtree)

Using the successor to replace the deleted node preserves the binary-search-tree property automatically: the successor is, by definition, the smallest key larger than every key in the deleted node's left subtree, and smaller than every remaining key in its right subtree, so it fits perfectly into the vacated position.

A unified helper procedure called TRANSPLANT is typically used to handle the mechanics of replacing one subtree with another throughout all three cases, simplifying the implementation by centralizing the pointer manipulation logic.

Since deletion involves at most a constant number of TREE-SUCCESSOR and pointer-update operations, each bounded by O(h), the entire deletion procedure runs in O(h) time.

The Critical Dependence on Tree Height

Every operation covered in this article — search, minimum, maximum, successor, insertion, and deletion — runs in time proportional to the tree's height h, not the number of elements n directly. This distinction is crucial: if the tree happens to be balanced, with height Θ(log n), every operation runs in Θ(log n) time, matching the efficiency of the best comparison-based structures. But if the tree becomes unbalanced — for instance, if elements are inserted in already-sorted order, producing a tree that degenerates into essentially a linked list — the height can grow to Θ(n), and every operation slows to Θ(n), no better than a simple linked list traversal.

Why This Motivates Balanced Search Trees

This vulnerability to becoming unbalanced under certain insertion orders is the central weakness of the plain binary search tree described in this article, and it directly motivates the more sophisticated self-balancing structures, such as red-black trees, covered next in this series. These structures add extra bookkeeping and rebalancing logic specifically to guarantee that the tree's height remains O(log n) regardless of the order in which elements are inserted or deleted, ensuring every operation described here retains its logarithmic efficiency under all circumstances, not merely favorable ones.