C Binary Search Tree

Search recursively, going left or right based on comparison. Insert is the same. Delete has three cases: leaf, one child, two children — the third uses the in-order successor.

We've seen BST insert and traversal. Today: search and delete — completing the BST API. Delete is the only tricky part.

Search

Node *search(Node *root, int value) {
  if (root == NULL || root->data == value) return root;
  if (value < root->data) return search(root->left, value);
  return search(root->right, value);
}

Three cases:

1. Empty tree or match: return root (NULL or the node).
2. Value smaller: search left.
3. Value larger: search right.

Returns the matching node (for "find and update") or NULL (for "not found").

For a balanced BST: O(log n). Each step halves the remaining tree.

find_min — leftmost node

Node *find_min(Node *root) {
  while (root->left != NULL) root = root->left;
  return root;
}

The smallest value in a BST is always the leftmost. Walk left until NULL.

For find_max: walk right.

Delete: three cases

Node *delete(Node *root, int value) {
  if (root == NULL) return NULL;

  if (value < root->data) {
    root->left = delete(root->left, value);
  } else if (value > root->data) {
    root->right = delete(root->right, value);
  } else {
    // Found it — three cases

    // Case 1: leaf or one child (right)
    if (root->left == NULL) {
      Node *temp = root->right;
      free(root);
      return temp;
    }
    // Case 2: one child (left)
    if (root->right == NULL) {
      Node *temp = root->left;
      free(root);
      return temp;
    }
    // Case 3: two children
    Node *min = find_min(root->right);
    root->data = min->data;
    root->right = delete(root->right, min->data);
  }
  return root;
}

Case 1 & 2: zero or one child

if (root->left == NULL) {
  Node *temp = root->right;
  free(root);
  return temp;
}

If the node has no left child, just promote the right child (which may be NULL — that's fine, replaces root with NULL = leaf delete).

Same idea if no right child — promote the left.

Case 3: two children

This is the hard case. The trick: find the in-order successor (smallest value in the right subtree), copy its data into the node we're deleting, then delete the successor (which has at most one child by definition).

Node *min = find_min(root->right);
root->data = min->data;
root->right = delete(root->right, min->data);

After this:

1. The node still exists structurally, but with a new value.
2. The successor is gone.
3. The BST invariant is preserved — successor was the smallest in right subtree, so it's larger than everything in left subtree and smaller than everything else in right subtree.

Alternative: use the in-order predecessor (largest in left subtree). Symmetric.

Why three cases

Walk through what happens for each:

Leaf:

... -> [50]                 ... -> NULL
delete 50

One child:

... -> [50]                 ... -> [70]
       /
     [70]

The single child takes the deleted node's place.

Two children:

       [50]                       [60]
      /    \                     /    \
   [30]   [70]      →         [30]   [70]
          /                          /
        [60]                       (60 was here, now gone)

Find min of right subtree (60), copy its value to current node, delete the original 60.

A complete example session

Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);

inorder(root);   // 20 30 40 50 60 70

root = delete(root, 30);   // delete with two children
inorder(root);             // 20 40 50 60 70

root = delete(root, 70);   // delete with one child (60)
inorder(root);             // 20 40 50 60

root = delete(root, 50);   // delete root
inorder(root);             // 20 40 60

The BST stays valid through every operation.

Search complexity

The "balanced" assumption is critical. Without rebalancing, sorted-order inserts produce a linear chain — O(n) operations. Real applications use self-balancing trees.

Self-balancing variants

AVL tree — strict balance: heights of children differ by at most 1. - Pros: very tight balance; lookups are fastest. - Cons: more rotations on insert/delete.

Red-Black tree — looser balance with color invariants. - Pros: fewer rotations; std::map and Java TreeMap use it. - Cons: slightly slower lookup than AVL.

Splay tree — rotates accessed nodes toward the root. - Pros: amortised O(log n); recently accessed items become fast. - Cons: every operation modifies the tree, even reads.

For C, the Linux kernel's rbtree.h is the canonical red-black implementation; you can drop it into projects.

Common mistakes

Forgetting to assign delete's return. delete(root, 5) doesn't update root. Use root = delete(root, 5).

Memory leak in two-child delete. Forgetting to delete the successor leaves it in the tree.

Search visiting both subtrees. A BST always picks left or right based on comparison. Visiting both is O(n) — wrong.

Inserting equal values inconsistently. Going always-right or always-left for equal values is fine; mixing breaks invariants.

Returning new root only sometimes. For consistency, always return root (even when unchanged). Caller assigns: root = delete(root, ...).

Not handling NULL inputs. delete(NULL, 5) should return NULL, not crash.

What's next

Episode 53: bubble sort. The simplest sorting algorithm — O(n²) but easy to understand.

Recap

BST search: walk left/right by comparison, O(log n) balanced. Delete cases: zero/one child (promote replacement); two children (copy in-order successor's value, delete successor). find_min walks leftmost. Always reassign root = delete(root, ...) — function may return a new root. For balanced performance, use self-balancing trees (AVL, red-black) — basic BSTs degenerate on sorted input.

Next episode: bubble sort.