Binary Search Tree

Store keys by shape so search, insert, and delete each walk a single path down the tree.

A binary search tree (BST) keeps numbers sorted *by shape*. Every node holds a key, and obeys one rule everywhere: all smaller keys live in its left branch, all larger keys in its right. That single invariant turns the tree into a decision diagram — at each node you compare once and step left or right, so you only ever walk *one path* from the root to where the answer lives.

The BST property is local but total

The rule holds at *every* node, not just the root — so the left subtree is itself a valid BST, and so is the right. That self-similarity is why every operation is naturally recursive: solve it at the root, then recurse into the one child that can contain the key.

Building one — insert by walking down

Insert 50, 30, 70, 20, 40, 60, 80 into an empty tree. Each new key starts at the root and steps left (smaller) or right (larger) until it falls off the tree into an empty slot, where it becomes a new leaf:

insert order: 50 30 70 20 40 60 80

          50
        /    \
      30      70
     /  \    /  \
   20   40 60   80

40 went: 40 < 50 -> left to 30; 40 > 30 -> right -> empty slot.

Searching is one comparison per level

1Start at the root.
2If the key equals the node's key -> found.
3If the key is smaller -> go to the left child.
4If the key is larger -> go to the right child.
5Hit an empty slot (no child) -> the key is not present.

Searching for 60: 60 > 50 go right to 70; 60 < 70 go left to 60 — found in 3 steps. The cost is the height of the tree, not the number of nodes.

Reading it back in sorted order

An in-order traversal — visit left branch, then the node, then right branch — emits a BST's keys from smallest to largest. For the tree above it prints 20 30 40 50 60 70 80. This is why a BST is sometimes described as a sorted structure you can also insert into cheaply.

function inorder(node, out) {
  if (!node) return;
  inorder(node.left, out);   // smaller keys first
  out.push(node.key);        // then this node
  inorder(node.right, out);  // then larger keys
}

Deleting a two-child node needs a stand-in

Removing a leaf is trivial, and a node with one child is replaced by that child. But a node with two children can't just vanish — replace its key with its in-order successor (the smallest key in its right subtree), then delete that successor, which always has at most one child.

Sorted input is the worst case

Insert 10, 20, 30, 40 in order and the tree degenerates into a right-leaning chain of height *n* — every search becomes O(n), no better than a linked list. Self-balancing variants (AVL, red-black) exist precisely to prevent this.

OperationTimeSpace

Search / insert / delete (balanced) · one path down; h = heightO(log n)O(h)

Same, but degenerate (sorted input) · tree becomes a chainO(n)O(n)

In-order traversal · visits every node, sortedO(n)O(h)

Check yourself

Why does an unbalanced BST built from already-sorted input lose its speed advantage?