AlgoScope

Binary Search Tree

structurebeginnerTime O(h)Space O(1)

Smaller values go left, larger go right. Every search is one path from the root, comparing once per node.

203035404550607080current

Delete 30. Start at the root and compare at every node.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 2, with their answers.

  1. At 50, looking for 30. Which way?

    • Go left
    • Go right
    • Found it

    Answer: Go left. 30 is smaller than 50, so the search goes left.

  2. At 30, looking for 30. Which way?

    • Go left
    • Go right
    • Found it

    Answer: Found it. 30 equals 30, so the search stops here.

How it runs, step by step

  1. Delete 30. Start at the root and compare at every node.

    Binary search tree with 9 nodes, root 50. Delete 30.

  2. 30 is smaller than 50: go left.

    Comparing 30 with node 50. 30 is smaller, so move to the left child, node 30.

  3. 30 equals 30. Found it.

    Comparing 30 with node 30. They match, so the search is over.

  4. 30 has two children. Find its successor: go right once, then left as far as possible.

    30 has two children. Looking for the successor, starting at the right child 40.

  5. 40 has a left child, so keep going left.

    Moving left from 40 to 35.

  6. 35 is the successor: the smallest value larger than 30. Unhook it.

    Successor is 35. It is detached from 40.

  7. 35 moves up into 30's spot and adopts its children. Order is preserved.

    30 is removed and 35 takes its place with the same children.

  8. Deleted 30. Inorder order is unchanged: 20, 35, 40, 45, 50, 60, 70, 80.

    Result: 30 deleted. The tree now has 8 nodes in sorted inorder.

Remember

  • Search, insert and delete all cost O(height). That is O(log n) while the tree stays balanced and O(n) once it degenerates into a chain.
  • New values always become leaves.
  • Deleting a node with two children replaces it with its inorder successor, so sorted order survives.

Topics covered

Related

Where this is used

Standard librariesOrdered maps and sets in standard libraries

Java's TreeMap is a red-black tree, and so is C++'s std::map in every major implementation: a BST that rotates after each change to hold its height down. A hash map beats them on a plain lookup, but it stores keys in no order at all, so it cannot answer floorKey, ceilingKey, a range view, or iterate everything in sorted order. Those all fall out of the BST invariant: standing at any node you already know which side the answer is on.

Operating systemsThe Linux CFS process scheduler

Each CPU's runnable tasks sit in a red-black tree keyed by virtual runtime, the CPU time a task has already had, scaled by its priority. CFS ran the smallest key next, which is the leftmost node, and the kernel caches a pointer to it so the pick costs nothing. When a task is descheduled its vruntime has changed, so it is removed and reinserted at its new position, which is why the ordering has to be cheap to maintain and not merely cheap to read. Linux 6.6 replaced CFS with EEVDF, which keeps the same tree but picks by virtual deadline instead of always taking the leftmost node.

Networkingepoll's interest list in the Linux kernel

An epoll instance keeps every watched file descriptor in a red-black tree, so epoll_ctl can add, modify or remove one registration in O(log n) with a hundred thousand sockets open. That is the fix for select and poll, which had to rescan the whole descriptor set on every single call. Readiness lives in a separate list, so the tree is touched only when the watched set changes, not on every event.

Language runtimesTreeified buckets in Java's HashMap

Since Java 8, a HashMap bucket that collects eight colliding entries converts its linked list into a red-black tree, provided the table already holds at least 64 slots - below that the map just resizes instead - and converts back when the bucket shrinks again. The point is the worst case: before that change, anyone who could choose keys that all hash to one bucket turned every lookup into a linear scan, so feeding in n such keys cost quadratic time. Ordering the bucket by hash, and by the key itself when the hashes tie and the key is comparable, makes it O(log n) instead, capping the damage without touching the normal case where a bucket holds one or two entries.

Why it works this way

Insertion order decides the shape, and sorted input is the worst case

The tree remembers nothing except the order values arrived in. Insert 1, 2, 3, 4 and every value goes right, so nothing ever branches. Random order is far kinder: a successful search then averages about 1.39 * log2 n comparisons and the height settles near 3 * log2 n. But real data rarely arrives randomly: timestamps, auto-increment ids and anything already sorted all build the same straight line. That is the whole reason AVL and red-black trees exist - they rebalance as values arrive, so the height stays logarithmic whatever order the values come in.

Why the inorder successor, and nothing else, can take a deleted node's place

The replacement has to be larger than everything in the left subtree and smaller than everything else in the right subtree, and only two values in the tree satisfy both: the largest on the left, the predecessor, and the smallest on the right, the successor. Either works, and the successor is just the usual convention. It is cheap because the smallest value in the right subtree is found by walking left until you cannot, so by definition it has no left child and removing it is the easy zero-or-one-child case. The two-children case therefore never has to be handled twice.

Checking each node against its own children is not enough

The obvious way to validate a BST - confirm node.left.value < node.value < node.right.value everywhere - accepts trees that are broken. Take root 8 with right child 10, and give 10 a left child of 6: that 6 passes its parent's local test, but it sits inside 8's right subtree where every value must exceed 8. The fix is to carry a range downwards, each call passing the (min, max) window its subtree is allowed to occupy and narrowing it at every step. An inorder walk that checks the values come out strictly increasing does the same job in one pass.

Where do duplicates go?

The insert above does nothing when value equals node.value, so duplicates are silently dropped, which is right for a set and wrong if you meant to count. The real options are to reject them, to keep a count field on the node, or to send equal values consistently to one side. The third is where it goes wrong quietly: search stops at the first equal value it meets, so the copies below it are never visited and a delete removes only the one it found. Whichever rule you pick, search, insert and delete all have to agree on it.

Read more

Next up