Binary search trees

A binary search tree adds a single invariant: for every node, everything in the left subtree is smaller and everything in the right subtree is larger. That one rule turns a tree into a searchable index.

Search and insert

function search(node, target) {
  while (node) {
    if (node.value === target) return node;
    node = target < node.value ? node.left : node.right;   // discard half
  }
  return null;
}

function insert(node, value) {
  if (!node) return { value, left: null, right: null };

  if (value < node.value) node.left = insert(node.left, value);
  else if (value > node.value) node.right = insert(node.right, value);

  return node;                       // equal values: ignore, or keep a count
}

Both are O(h): O(log n) on a balanced tree, O(n) on a degenerate one.

Deletion, and its three cases

The only fiddly operation:

1. No children — remove it.
2. One child — replace the node with that child.
3. Two children — replace its value with its inorder successor (the smallest value in the right subtree), then delete that successor, which by construction has at most one child.

function remove(node, value) {
  if (!node) return null;

  if (value < node.value) node.left = remove(node.left, value);
  else if (value > node.value) node.right = remove(node.right, value);
  else {
    if (!node.left) return node.right;      // cases 1 and 2
    if (!node.right) return node.left;

    let successor = node.right;             // case 3
    while (successor.left) successor = successor.left;

    node.value = successor.value;
    node.right = remove(node.right, successor.value);
  }

  return node;
}

Validating a BST

The classic trap: checking only left.value < node.value < right.value locally. That passes trees which are not BSTs — a deep left descendant can still exceed an ancestor. Carry bounds down instead:

const isBST = (node, min = -Infinity, max = Infinity) =>
  !node ||
  (node.value > min &&
    node.value < max &&
    isBST(node.left, min, node.value) &&
    isBST(node.right, node.value, max));

Equivalently: an inorder traversal of a valid BST is strictly increasing.

What a BST gives you that a hash map cannot

Ordered iteration, minimum and maximum in O(h), predecessor and successor, and range queries — "all keys between 40 and 60" — in O(h + k). Those are exactly the queries a database index must answer, which is why indexes are trees and not hash tables.