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.

20304050607080current

Insert 65. 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 3, with their answers.

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

    • Go left
    • Go right
    • Found it

    Answer: Go right. 65 is larger than 50, so the search goes right.

  2. At 70, looking for 65. Which way?

    • Go left
    • Go right
    • Found it

    Answer: Go left. 65 is smaller than 70, so the search goes left.

  3. At 60, looking for 65. Which way?

    • Go left
    • Go right
    • Found it

    Answer: Go right. 65 is larger than 60, so the search goes right.

How it runs, step by step

  1. Insert 65. Start at the root and compare at every node.

    Binary search tree with 7 nodes, root 50. Insert 65.

  2. 65 is larger than 50: go right.

    Comparing 65 with node 50. 65 is larger, so move to the right child, node 70.

  3. 65 is smaller than 70: go left.

    Comparing 65 with node 70. 65 is smaller, so move to the left child, node 60.

  4. 65 is larger than 60, but there is no right child.

    Comparing 65 with node 60. 65 is larger, so move to the right child. There is none.

  5. The right child of 60 is empty: 65 goes there as a new leaf.

    65 inserted as the right child of 60.

  6. Inserted after 3 comparisons. New values always become leaves.

    Result: 65 inserted. The tree has 8 nodes.

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