hashing and treessolid

Binary Search Trees and the Degenerate Case

The rule fits in one sentence: every value in a node's left subtree is smaller than the node's value, every value in its right subtree is larger, and this holds at every node in the tree. That's the entire upgrade. The node is unchanged from lesson 13, a value and two pointers; no new fields, no new memory layout. Just a law about where values are allowed to live. A binary tree that obeys it is a binary search tree (BST), and the name is earned literally: by the end of this lesson you'll see that a BST is lesson 8's binary search, frozen into a structure.

Here is the tree this whole lesson lives in. Check the rule anywhere on it:

        8
      /   \
     3     12
    / \    /  \
   1   6  10   14
      /
     4

At the root: everything in 8's left subtree (1, 3, 4, 6) is smaller than 8; everything in its right subtree (10, 12, 14) is larger. At node 3: its left holds only 1 (smaller), its right holds 6 and 4 (both larger than 3, and notice, both also smaller than 8, because they live inside 8's left subtree too). At node 6: 4 on the left, nothing on the right. Every node passes. The rule is called the BST invariant, and "invariant" is lesson 8's word, used deliberately: it's the property that is true before and after every operation, the thing every algorithm in this lesson leans on.

The rule is about subtrees, not children

Before the rule pays out, the mistake nearly every student makes with it, because the wrong reading is so comfortable: "smaller child on the left, bigger child on the right." The rule does not say child. It says subtree, the entire subtree. Here is the classic wrong tree:

        8
      /   \
     3     12
    / \
   1   9      <- 9 > 3, locally fine. 9 > 8, broken.

Check every parent-child pair locally: 3 < 8, fine. 12 > 8, fine. 1 < 3, fine. 9 > 3, fine. Every local check passes, and the tree is broken, because 9 sits inside 8's left subtree and 9 > 8. A checker that only compares each node against its children declares this tree valid. It is not, and the proof is operational: search for 9. Start at the root: 9 > 8, so the rule says go right. At 12: 9 < 12, go left. Null. Not found. The 9 is in the tree, and an honest search can never reach it, because it lives on a side it has no business being on.

So the invariant is really a statement about ranges. The root constrains all of its descendants: every node in 8's left subtree, however deep, must be below 8. Each step down narrows the legal window. Node 3 lives in the range (negative infinity, 8); its right child lives in (3, 8), which is exactly why 6 is legal there and 9 was not. The correct validity check carries that window down the tree:

function is_bst(t, lo, hi):           # lo and hi start at -inf, +inf
    if t is empty: return true
    if t.value <= lo or t.value >= hi: return false
    return is_bst(t.left, lo, t.value) and is_bst(t.right, t.value, hi)

Lesson 13's three-line skeleton again: handle empty, trust the subtrees, combine. The only news is the window threading through.

Search: binary search, frozen solid

Now watch what an intact invariant buys. Search the real tree for 10. At 8: 10 > 8, and the rule guarantees everything in the left subtree is smaller than 8, so 10 cannot be there. One comparison just discarded 1, 3, 4, and 6: four nodes, unexamined. At 12: 10 < 12, so 12's right subtree is out; 14, discarded. Step left: 10. Found. Three comparisons for an eight-node tree.

Say it in lesson 8's words, verbatim: discard half per comparison, legal because of sortedness. On the array, sortedness let you jump to the middle and throw away a half. Here the invariant plays the same role, and the structure has pre-positioned the midpoints: the root is the middle element, its children are the middles of the two halves, and every node is a midpoint comparison, computed once and frozen into a pointer. That's the identity at the center of this lesson. A sorted array runs binary search by arithmetic on indices; a BST runs it by following pointers; the comparisons are the same comparisons.

Misses are just as clean. Search for 5: 5 < 8, left. 5 > 3, right. 5 < 6, left. 5 > 4, right... null. You fell off the tree, and you know 5 is absent after four comparisons, without glancing at anything else.

function search(t, target):
    if t is empty: return false       # fell off: not present
    if target == t.value: return true
    if target < t.value: return search(t.left, target)
    else:                return search(t.right, target)

Insert, min, max: all O(height)

Insert is a search that refuses to take no for an answer. Insert 7: run the search. 7 < 8, left. 7 > 3, right. 7 > 6, right... null. You fell off, so attach 7 exactly where you fell: new leaf, right child of 6. That placement is why insert preserves the invariant for free: the search path you just walked is the path every future search for 7 will walk, so you've stored the key precisely where it will be looked for.

function insert(t, value):
    if t is empty: return new node(value)      # fell off: attach here
    if value < t.value: t.left  = insert(t.left, value)
    if value > t.value: t.right = insert(t.right, value)
    return t                                   # equal: already present, ignore

Two freebies come with the invariant. The smallest key: smaller is always left, so walk left until you can't (here, 1). The largest: walk right (14). No comparisons needed, just follow the wall.

Now price everything so far. Search, insert, min, max: each walks a single path from the root toward a leaf, so each costs the length of that path: O(height). And this lesson is going to be stubborn about writing it that way: height, not log n. On this tree the height is 3 and 3 is about the log of the node count, so the two feel like the same word. They are not. Nothing built so far guarantees they stay together, and the back half of this lesson is about exactly how far apart they can get.

The gun fires: in-order is sorted

Lesson 13 showed you a walk that produced nothing: left, node, right, and out came an arbitrary shuffle (7 9 1 4 2 8), with instructions to remember it anyway. Run it on this tree, the 9-node version with 7 inserted. Drain the left subtree, visit the node, drain the right. Deepest left first: 1. Then 3. Then 3's right subtree: 4, 6, 7. That closes everything under 3, so: 8. Then the right side: 10, 12, 14.

1 3 4 6 7 8 10 12 14. Sorted. The walk fired, and nothing about the walk changed: same six lines as last lesson. The only thing that changed is where values are allowed to live.

Why it works falls straight out of the invariant, by the same leap of faith every recursion since lesson 9 has used. At any node, everything smaller sits in the left subtree, and in-order visits all of it first; then the node; then everything larger. Trust each subtree to flatten itself sorted, and the node lands exactly between its two sorted halves. That holds at every level, so the whole output is sorted. The clean way to say it: a BST is a sorted sequence stored as a tree, and in-order is the flattening. (It's also a free correctness probe: if an in-order walk of your tree ever comes out unsorted, the invariant is broken somewhere, which is exactly how the wrong tree above confesses: its in-order is 1 3 9 8 12.)

What order buys

Sorted, kept live under inserts and deletes, is exactly what lesson 12's hash table couldn't sell you: it scattered keys on purpose and gave up all order. Collect what the BST sells instead.

Range queries. Every key between 4 and 11: walk in-order, but prune with the invariant. At 8, both sides may hold answers, descend both. At 3: 3 < 4, so 3's left subtree, everything smaller than 3, cannot contain a single answer; skip it, never touch the 1. At 12: descend left for 10, but 12 > 11 means 12's right subtree is dead; never touch 14. Out comes 4, 6, 7, 8, 10. The walk visits the k answers plus one thin path around the boundary: O(height + k), not O(n).

Floor, ceiling, nearest. Ask for 9, which isn't there. Walk its search path and keep two notes: the last node you left going right (that node is smaller than 9), the last you left going left (larger). Fall off, and the notes read 8 and 10: the floor and ceiling of 9, off one path, O(height).

Sorted iteration. Free; that's the in-order walk.

The honest ledger, side by side:

operation	hash table (lesson 12)	BST (height h)
lookup / insert / delete	O(1) average	O(h)
smallest / largest key	O(n), full scan	O(h)
floor / ceiling / nearest	not a concept	O(h)
range query, k results	O(n), full scan	O(h + k)
iterate in sorted order	O(n log n), sort first	O(n), in-order

Two different products. The hash table wins raw lookups and nothing else; the moment any question contains the words "smallest", "between", "nearest", or "in order", the tree is the only one of the two with an answer. Choosing between them is a real production decision, and now you own both sides of it.

Delete: three cases

Delete is where trees get honest, because you can't just unhook a node that's holding a subtree up. Three cases, in rising order of trouble, all on the 9-node tree.

Case 1, a leaf. Delete 4. No children, nothing depends on it: null out the parent's pointer. Done.

Case 2, one child. With 4 gone, 6 has only the 7. Delete 6: splice, pointing 3's right pointer past 6 straight at 7. This is lesson 5's linked list deletion, and the invariant survives because 7 already lived in 3's right subtree: bigger than 3, smaller than 8, both still true in its new position.

Case 3, two children. Delete 8, the root. Both subtrees are populated and orphaning them is not an option. So don't delete the node; replace its value, with the one value that can legally sit above both subtrees. The replacement must be bigger than everything in the left subtree and smaller than everything remaining in the right. That is the smallest value in the right subtree: the in-order successor, the key that comes immediately after 8 in sorted order. Find it by walking right once, then left to the wall: 10. Copy 10 into the root. Now 10 appears twice, so delete the old 10 from the right subtree, and here's the detail that keeps this from spiraling: the successor is the leftmost node of its subtree, so it has no left child, which means deleting it is always case 1 or case 2. The recursion bottoms out immediately. One path down to find the successor, one path to clean up: still O(height).

function delete(t, value):
    if t is empty: return empty                  # not found
    if value < t.value: t.left  = delete(t.left, value);  return t
    if value > t.value: t.right = delete(t.right, value); return t
    # found it:
    if t.left is empty:  return t.right          # leaf or one child
    if t.right is empty: return t.left
    s = min_node(t.right)                        # in-order successor
    t.value = s.value
    t.right = delete(t.right, s.value)           # always an easy case
    return t

(The symmetric choice, the in-order predecessor, largest in the left subtree, works identically; libraries alternate or pick one.)

The degenerate case

Now the second half of the title. Empty tree. Insert the most innocent input in the world: 1, 2, 3, 4, 5, in that order.

1 becomes the root. 2 is bigger: right child. 3 is bigger than 1, bigger than 2: hangs under 2. 4 walks the whole chain and hangs off 3. 5 walks further still.

Nothing branched, not once. Every node has exactly one child, leaning right, all the way down. Lesson 13 called this shape a linked list in a costume and noted the definition allows it. Here's the part lesson 13 couldn't say yet: the invariant allows it too. Check the rule at every node of that chain: it passes. This is a perfectly legal binary search tree, with height n.

So search is O(n). Insert is O(n). Min, max, delete: O(n). And building it is worse: the k-th insert walks k nodes, so n sorted inserts cost about n²/2 total. Fifty thousand keys, over a billion steps: the GTA shape from lesson 1, growing quietly. Every promise this lesson made said O(height), and this is why the lesson was stubborn about the word. The promises all still hold. The height is just n.

Sit with how cruel the trigger is. Sorted input. Lesson 8 built binary search on sortedness: on an array, sorted order is the precondition that makes halving legal, the best thing input can possibly be. Feed the same sorted sequence into a BST one key at a time and it produces the one shape where halving never happens. The structure that froze binary search, killed by binary search's favorite food. And you have seen this exact pathology in another costume: lesson 10's quicksort with a first-element pivot, fed sorted input. Same disease, a splitter that lands at the edge instead of the middle, every single time, collapsing O(n log n) to O(n²). In the BST, every insert's "split" puts all future keys on one side.

What makes this a production story rather than a textbook footnote: sorted and nearly-sorted input is not a corner case, it's the default arrival order of real data. Auto-increment IDs come out of the database ascending. Timestamps arrive in order; that is what time does. Log lines, event streams, Kafka offsets, order numbers: real-world keys overwhelmingly show up ascending. Insert a day of production events into a naive BST and you have not built a tree. You've built the slowest linked list ever made.

Balance, named but not built

So how is this structure everywhere? Two outs.

The first is luck, formalized. If keys arrive in random order, the expected height of the tree is O(log n), a small constant times the log; the chain shape requires an astronomically unlucky permutation. True theorem (stated here, not proven), real comfort for some workloads, and a useless guarantee in production, because you don't choose your arrival order. The stream is the stream.

The second out is the real one: don't hope for balance, enforce it. There is a family of trees that detect when a subtree leans too far and repair the shape on the spot, after every insert and delete: AVL trees and red-black trees are the famous members. The repair operations, rotations, are a subject of their own and the opening lesson of dsa-patterns; today, just know the contract: same invariant, same search, same in-order walk, but height pinned at O(log n) no matter what order keys arrive in, sorted streams included.

And those are the trees that actually ship. C++'s std::map and std::set are red-black trees (the standard's iterator and complexity guarantees effectively force it). Java's TreeMap and TreeSet: red-black trees. The Linux kernel keeps red-black trees for its schedulers and timers. Every time you've used an ordered map, you were holding this lesson's structure under a maintenance contract. Plain unbalanced BSTs earn their keep only where you control the input: if you have all n keys up front and sorted, you can build a perfectly balanced tree directly, by picking the middle element as the root and recursing on the halves, which is binary search's index arithmetic materialized into pointers, one more angle on the same identity. (The other big ordered structure in production, the B-tree that runs your database's indexes, is the same idea rebuilt for disk, and it's dsa-patterns territory.)

The real code

Videos stay in pseudocode; here is the full structure in the three course languages: insert, search, min, in-order, and delete.

interface TreeNode {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}
 
function insert(t: TreeNode | null, value: number): TreeNode {
  if (t === null) return { value, left: null, right: null } // fell off: attach here
  if (value < t.value) t.left = insert(t.left, value)
  else if (value > t.value) t.right = insert(t.right, value)
  return t // equal: already present, no duplicates
}
 
function search(t: TreeNode | null, target: number): boolean {
  if (t === null) return false // fell off: absent, guaranteed
  if (target === t.value) return true
  return target < t.value ? search(t.left, target) : search(t.right, target)
}
 
function minNode(t: TreeNode): TreeNode {
  while (t.left !== null) t = t.left // smaller is always left
  return t
}
 
function inorder(t: TreeNode | null, out: number[] = []): number[] {
  if (t === null) return out
  inorder(t.left, out)
  out.push(t.value) // lesson 13's walk, now emitting sorted order
  inorder(t.right, out)
  return out
}
 
function remove(t: TreeNode | null, value: number): TreeNode | null {
  if (t === null) return null // not found: nothing to do
  if (value < t.value) {
    t.left = remove(t.left, value)
  } else if (value > t.value) {
    t.right = remove(t.right, value)
  } else if (t.left === null) {
    return t.right // case 1 and 2: leaf or one child, splice
  } else if (t.right === null) {
    return t.left
  } else {
    const s = minNode(t.right) // case 3: in-order successor
    t.value = s.value
    t.right = remove(t.right, s.value) // successor has no left child: easy case
  }
  return t
}

type TreeNode struct {
	Value int
	Left  *TreeNode
	Right *TreeNode
}
 
func insert(t *TreeNode, value int) *TreeNode {
	if t == nil {
		return &TreeNode{Value: value} // fell off: attach here
	}
	if value < t.Value {
		t.Left = insert(t.Left, value)
	} else if value > t.Value {
		t.Right = insert(t.Right, value)
	}
	return t
}
 
func search(t *TreeNode, target int) bool {
	for t != nil { // iterative: one descending path, no frames
		if target == t.Value {
			return true
		}
		if target < t.Value {
			t = t.Left
		} else {
			t = t.Right
		}
	}
	return false
}
 
func minNode(t *TreeNode) *TreeNode {
	for t.Left != nil {
		t = t.Left
	}
	return t
}
 
func inorder(t *TreeNode, out *[]int) {
	if t == nil {
		return
	}
	inorder(t.Left, out)
	*out = append(*out, t.Value)
	inorder(t.Right, out)
}
 
func remove(t *TreeNode, value int) *TreeNode {
	if t == nil {
		return nil
	}
	switch {
	case value < t.Value:
		t.Left = remove(t.Left, value)
	case value > t.Value:
		t.Right = remove(t.Right, value)
	case t.Left == nil: // found: leaf or one child
		return t.Right
	case t.Right == nil:
		return t.Left
	default: // found: two children
		s := minNode(t.Right)
		t.Value = s.Value
		t.Right = remove(t.Right, s.Value)
	}
	return t
}

struct TreeNode {
    int value;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;
};
 
TreeNode* insert(TreeNode* t, int value) {
    if (t == nullptr) return new TreeNode{value};
    if (value < t->value) t->left = insert(t->left, value);
    else if (value > t->value) t->right = insert(t->right, value);
    return t;
}
 
bool search(const TreeNode* t, int target) {
    while (t != nullptr) {
        if (target == t->value) return true;
        t = target < t->value ? t->left : t->right;
    }
    return false;
}
 
TreeNode* min_node(TreeNode* t) {
    while (t->left != nullptr) t = t->left;
    return t;
}
 
void inorder(const TreeNode* t, std::vector<int>& out) {
    if (t == nullptr) return;
    inorder(t->left, out);
    out.push_back(t->value);
    inorder(t->right, out);
}
 
TreeNode* remove(TreeNode* t, int value) {
    if (t == nullptr) return nullptr;
    if (value < t->value) { t->left = remove(t->left, value); return t; }
    if (value > t->value) { t->right = remove(t->right, value); return t; }
    if (t->left == nullptr)  { TreeNode* r = t->right; delete t; return r; }
    if (t->right == nullptr) { TreeNode* l = t->left;  delete t; return l; }
    TreeNode* s = min_node(t->right);   // two children: successor
    t->value = s->value;
    t->right = remove(t->right, s->value);
    return t;
}

Read insert against the pseudocode: the recursion returns the subtree, so t.left = insert(t.left, value) re-attaches the (possibly new) child on the way back up, and the null base case is the "fell off, attach here" moment. remove is the three cases in order: the first two else if arms handle leaf-and-one-child by returning the other side (returning null for a leaf is the same splice), and the final arm copies the successor's value and recurses into the right subtree, where it is guaranteed to hit an easy case.

The Go search is written as a loop on purpose: search never backtracks, it only descends, so the recursion is trivially a for loop with pointer reassignment, no stack frames at all. (Insert and delete stay recursive here because the return-and-reattach idiom keeps them short; both have well-known iterative forms.) The switch in remove reads as the case analysis it is.

C++ adds the obligation the garbage-collected languages hide: the spliced-out node must be deleted, and only that node. In the two-children case nothing is freed at the found node at all, only a value is overwritten; the actual delete happens down in the right subtree when the recursion reaches the old successor, which lands in one of the first two arms. Lesson 13's free_tree (post-order, children before parent) still applies for tearing down the whole structure.

The degenerate case, demonstrated with lesson 13's height function:

function height(t: TreeNode | null): number {
  if (t === null) return -1
  return 1 + Math.max(height(t.left), height(t.right))
}
 
let root: TreeNode | null = null
for (const v of [1, 2, 3, 4, 5]) root = insert(root, v)
 
height(root) // 4: every insert went right, the "tree" is a chain
inorder(root) // [1, 2, 3, 4, 5]: the invariant holds, the shape is ruined

Five sorted inserts, height 4: height equals n minus 1, the chain. The in-order output is still perfectly sorted, which is the point: degeneracy is not a correctness bug, it is a performance collapse with all invariants intact, which is exactly why nothing crashes and nobody notices until n grows.

Where this shows up in production

std::map, std::set, Java TreeMap/TreeSet. Red-black trees, every one. Ordered iteration, lower_bound/ceilingKey (this lesson's floor/ceiling), and range scans are this lesson's operations with balance enforced underneath.
The Linux kernel. Red-black trees schedule processes and manage timers and virtual memory areas: workloads where keys (deadlines, addresses) arrive nearly sorted, the exact input a naive BST dies on, which is why the kernel ships the self-balancing variant.
The degenerate case as a real failure mode. Insert auto-increment primary keys, timestamps, or log offsets into any unbalanced tree and you get the chain. This is the same pathology that forced lesson 10's quicksort to abandon the first-element pivot: production data is sorted-ish by default, so structures that assume random order must either randomize or rebalance.
Build-from-sorted. Loading a sorted dataset into a perfectly balanced tree by recursive midpoints is a standard bulk-load trick, and databases do the disk version of it when building B-tree indexes from sorted runs.

Total order, and what it costs

The ledger for the lesson. One rule, the BST invariant, and last lesson's inert structure became a search structure: search, insert, min, max, floor, ceiling in O(height); range queries in O(height + k); sorted iteration for free, because in-order plus the invariant equals sorted, the gun lesson 13 planted. Delete takes three cases and one clever successor swap. And the whole contract hangs on one word, height, which sorted input, the most ordinary input in production, stretches to n. Balanced trees pin it back to log n, and that machinery is dsa-patterns' opening act.

But notice what you're paying for: a BST maintains the total order of every key, all the time, whether or not you ever ask. Some of the most common workloads never do. A scheduler doesn't want all jobs in order; it only ever asks one question, what's next: the smallest deadline, the highest priority, over and over. Keep total order for that and you're buying the whole menu to eat one dish. Relax the invariant to something weaker, just "parent beats children", and the tree stops needing pointers entirely: it packs into a plain array, the complete-tree trick lesson 13 teased, with the smallest element always sitting at index zero. That structure is the heap, it powers priority queues and one more O(n log n) sort, and it's next.

Command Palette