Binary Search Trees

By the end of this lesson you will be able to explain the BST property, trace every core operation — walk, search, minimum/maximum, successor/predecessor, insert, and delete (all the cases, with the transplant helper) — line by line on a picture of the tree, implement each one in idiomatic Dart, and explain why a "randomly built" BST is expected to stay shallow (O(lg n)) even though a badly built one can degrade to a straight line (Θ(n)).

0. What is a binary search tree?

A BST node stores a key (what we search by), optional satellite data (whatever else the node carries — a name, a price, a whole record), and three pointers: left, right, and parent. A pointer that has nothing to point to is written NIL in the pseudocode — in Dart that is null. The root's parent is NIL, and the tree object only remembers its root.

Because of the BST property, five queries all become "follow one path down (or up) the tree, making a left/right decision at each node": search, minimum, maximum, successor, predecessor — plus insert and delete for building and shrinking the tree. Every one of these runs in time proportional to the tree's height h (the number of edges on the longest root-to-leaf path) — written O(h). A perfectly balanced tree on n nodes has h = Θ(lg n) (fast!); a badly built one (for example keys inserted in already-sorted order) degenerates into a straight chain with h = Θ(n) (as slow as a linked list). This lesson is largely about that gap, and section 4 shows that if you build the tree by inserting keys in a random order, you get O(lg n) height on average — no rebalancing required.

The bounds above, as code. Height h counts edges (empty tree −1, one node 0). A height-h binary tree holds at most 2h+1 − 1 nodes, so h ≥ lg n (precisely h ≥ ⌊lg n⌋); sorted insertion order gives the chain with the largest possible height n − 1. The code below computes all three and the checks in verify/c12.dart confirm them for every n ≤ 3000. Inputs: any n ≥ 1; n = 106 → ⌊lg n⌋ = 19 versus a chain height of 999,999.

1. The BST property & inorderWalk

inorderWalk(x)

Recurse left, print the current node, recurse right. The base case is x = NIL — an empty (sub)tree prints nothing.

Input size → what’s feasible: n = 106 nodes → 2n + 1 ≈ 2·106 calls ≈ 0.02 s at ~10⁸ simple steps/s, whatever the shape. But the recursion depth equals h: ≈ 60 for a random tree, 10⁶ for a chain — and the Dart stack is limited (typically on the order of 10⁴ nested calls; the exact limit depends on the platform and the size of each frame), so for chain-like inputs deeper than a few thousand levels use an explicit stack (see the Kth-smallest question).

Fact A (walk cost). If x is the root of an n-node subtree, inorderWalk(x) takes Θ(n) time. Why: let T(n) be the time on an n-node subtree. If the left subtree has k nodes, the right has n − k − 1, and printing the root plus the constant overhead of one call costs some constant d: T(n) = T(k) + T(n−k−1) + d. By substitution (guess T(n) ≤ (c+d)n + c and check the induction), this solves to T(n) = Θ(n) for any split k — the shape of the tree never changes the asymptotic cost of a full walk, only how it is distributed between the two recursive calls. A second way to see it: every one of the n nodes is entered once and every one of the n + 1 empty child slots is entered once, so the walk makes exactly 2n + 1 calls. In code: walkCalls counts every call (the n keys plus n + 1 NIL calls = 2n + 1), and walkTime evaluates the recurrence for three different split rules and checks it equals (c + d)·n + c exactly (with c = 3, d = 2: 5n + 3; for n = 10 that is 53).

Dart implementation (idiomatic, pointer-based). Translation note: BST algorithms have no array to re-index — the pseudocode's NIL pointer becomes Dart's null, and a node's .left/.right/.parent fields become ordinary nullable fields on a class (BSTNode<T>?). There is no numeric-offset translation to do at all, unlike the array-based algorithms — the whole appeal of a linked structure is that positions are pointers, not numbers.

preorderWalk(x) and postorderWalk(x)

Same recursion, different moment for the print x.key line. Preorder: print x first, then the left subtree, then the right subtree. Postorder: left subtree, right subtree, then x last. Only inorder gives sorted output. On the 12-key example tree built in section 2, preorder prints 50, 30, 20, 10, 25, 40, 45, 42, 70, 60, 65, 80 and postorder prints 10, 25, 20, 42, 45, 40, 30, 65, 60, 80, 70, 50 (both checked in verify/c12.dart). Like inorder they take Θ(n) time: each of the n nodes is visited once and each NIL once.

// preorderWalk(x)                  // postorderWalk(x)
if x ≠ NIL:                         if x ≠ NIL:
    print x.key                         postorderWalk(x.left)
    preorderWalk(x.left)                postorderWalk(x.right)
    preorderWalk(x.right)               print x.key

Input size → what’s feasible: same as inorderWalk: n = 106 → ≈ 2·106 calls (0.02 s), recursion depth h (keep it under a few thousand; the exact limit depends on the platform). Preorder is what you store to rebuild a BST (see the serialize question), postorder is what you use to free/delete a tree bottom-up.

2. Querying a binary search tree

All five queries below run on the same 12-key example tree, built by inserting 50, 30, 70, 20, 40, 60, 80, 10, 25, 45, 42, 65 one at a time into an empty tree (you will build exactly this tree yourself in section 3's insert animation). Every query here costs O(h) — Fact B. The tree is one line of Dart: buildTree([50, 30, 70, 20, 40, 60, 80, 10, 25, 45, 42, 65]), and its height is 4.

searchRecursive(x, k)

Compare k to the current node's key; if equal (or the branch ran out), stop; otherwise recurse into whichever side the BST property says k must live in.

Input size → what’s feasible: n = 106 keys, random-order build → h ≈ 3·lg n ≈ 60 → 105 lookups ≈ 6·106 steps, instant. The same keys built from sorted input → chain, h = 106 → 105 lookups = 1011 steps, too slow (shuffle first, or use a self-balancing tree). Recursive form needs stack depth h; use the iterative form once h can reach a few thousand.

search(x, k) — iterative

Same idea, no call stack: keep overwriting x as you step down, until x is NIL (miss) or holds k (hit).

Input size → what’s feasible: same arithmetic as the recursive version (O(h) time) but O(1) extra space and no stack-depth limit, so it is safe for any n up to 106 and any height.

minimum(x) and maximum(x)

Input size → what’s feasible: O(h) and O(1) space: n = 106 random-order keys → about 60 pointer moves per call, so 105 calls ≈ 6·106 steps; on a left chain it is n = 106 moves per call, so 105 calls = 1011, too slow.

successor(x) — the next-larger key

Two cases. (1) If x has a right subtree, its successor is simply the smallest key in that subtree (minimum(x.right)) — the next value up must be the smallest thing bigger than x itself. (2) If x has no right subtree, its successor is the lowest ancestor whose left subtree contains x — found by walking up parent pointers as long as you keep arriving from the right side, and stopping the moment you arrive from the left side.

Input size → what’s feasible: one call costs at most h pointer moves (≈ 60 for n = 106 random keys); listing the whole tree by calling it n times in a row costs Θ(n) in total (each edge of the tree is walked at most twice), i.e. ≈ 2·106 moves — far below the naive bound n·h = 6·107.

predecessor(x) — the next-smaller key

Mirror image of successor: if x has a left subtree, the predecessor is maximum(x.left); otherwise walk up until arriving from a right child.

Input size → what’s feasible: identical to successor: O(h) per call, O(1) space; n = 106 random keys → ≈ 60 moves per call.

Fact B as code. searchPath, insertSteps, minSteps and successorSteps count how many nodes/pointer moves each operation uses. On the example tree searchPath(canon, 43) is [50, 30, 40, 45, 42] (5 nodes, a miss), searchPath(canon, 50) is [50] (best case, 1 node) and searchPath(canon, 45) is [50, 30, 40, 45]. The checks confirm every count is at most h + 1 on random trees and chains, and that searching the last key of a 1000-node chain really touches n = h + 1 = 1000 nodes.

3. Insertion and deletion

insert(tree, key)

Input size → what’s feasible: n = 105 keys in random order → average insert depth ≈ 20 (exact value 20.2 from the recurrence in section 4) → ≈ 2·106 steps total, instant. The same keys in sorted order → n(n − 1)/2 = 5·109 steps (≈ 50 s) → shuffle first or use a balanced tree.

Loop invariant for the descent: before each iteration of the while loop, x is the root of the subtree in which the new key must end up (if the BST property holds for the rest of the tree), and y is either NIL (we have not moved yet) or x's parent. When the loop ends (x = NIL), y is exactly the node that should become the new node's parent, and the BST property is preserved by attaching the new node on whichever side matches the last comparison.

transplant(tree, u, v) — the delete helper

Input size → what’s feasible: always O(1) — a handful of pointer assignments — so the input size is irrelevant: 106 transplants ≈ 107 assignments ≈ 0.1 s.

delete(tree, z) — the cases

Deleting a node with two children is the hard part, because you cannot just remove it — something has to take its place while keeping the BST property intact. The delete procedure splits into cases:

1. Case 1 — z.left = NIL: (this covers both "z is a leaf" and "z has only a right child") just splice in z.right where z was: transplant(tree, z, z.right).
2. Case 2 — z.right = NIL (but z has a left child): symmetric — splice in z.left: transplant(tree, z, z.left).
3. Case 3/4 — z has two children: find z's successor y = minimum(z.right) (guaranteed to have no left child, since it is a leftmost node). y takes z's exact place. Case 3: if y is z's direct right child, one transplant does it. Case 4: if y is further down, y must first be spliced out of its own spot (a second transplant, giving y's old spot to y.right) before it can be moved up into z's place.

Input size → what’s feasible: O(h) per delete (one minimum call in cases 3/4, everything else O(1)): n = 105 random-order keys → ≈ 50 steps per delete, 104 deletes ≈ 5·105 steps. Never delete from a chain-shaped tree in a loop: 104 deletes × h = 105 = 109.

Which case applies, as code. deleteCase(z) returns 1 when z.left = NIL, 2 when only z.right = NIL, and for two children 3 if the successor is z's direct right child, else 4. On the example tree: key 10 → case 1 (leaf), 40 → case 1 (right child only), 45 → case 2, 30 → case 3, 50 → case 4; the checks also delete every key of 300 random trees in random order and confirm the BST property and the remaining keys after each delete, with all four cases occurring.

4. Randomly built binary search trees

How many shapes are there? The number of distinct binary-tree shapes with n nodes is bn = Σk=0n−1 bk·bn−1−k, b0 = 1 (the left subtree has k nodes, the right n−1−k): 1, 1, 2, 5, 14, 42, 132, …, the Catalan numbers C(2n, n)/(n+1) ≈ 4n/(√π·n3/2). In code, over all 3! = 6 insertion orders of three keys the balanced 3-node shape appears twice (probability 2/6 = 1/3), the four chains once each (1/6), whereas a uniformly random shape would give each of the 5 shapes 1/5.

Fact D (random-build height). The expected height of a randomly built BST on n distinct keys is O(lg n). The proof sketch: let X_n be the height and Y_n = 2^{X_n} (an "exponential height" that tames the very-skewed-tail cases). If the root ends up being the i-th smallest key (equally likely to be any of the n positions), then Y_n = 2·max(Y_{i−1}, Y_{n−i}). Averaging over all equally likely choices of i, and bounding the resulting recurrence, gives E[Y_n] = O(n³); then Jensen's inequality (2^x is convex, so 2^{E[X_n]} ≤ E[Y_n]) converts that back into E[X_n] = O(lg n).

Input size → what’s feasible: n = 106 keys: E[height] ≈ 3·lg n ≈ 60, average node depth ≈ 25 (exact: 24.8 for n = 106 from the recurrence below; 2 ln n = 27.6 is the leading term), so build time ≈ n × 25 ≈ 2.5·107 steps. Sorted input of n = 105 instead costs 5·109: shuffle the keys first (O(n)) or use a self-balancing tree.

The numbers behind Fact D, computed. (1) randomBuildHeights builds seeded random BSTs and returns their heights; every height lies between ⌊lg n⌋ and n − 1, and the average sits near 3 lg n (for n = 100 it is ≈ 12 versus lg n ≈ 6.6 and chain height 99).

(2) Average depth ≈ 2 ln n. The root is the i-th smallest key (i = 1..n, uniformly likely). Every other node is one level deeper than inside its own subtree, so the expected total depth satisfies P(n) = (n − 1) + (2/n)·Σi=0n−1 P(i) with P(0) = 0. It solves to P(n) = 2(n + 1)Hn − 4n (Hn the harmonic number), so the average depth is P(n)/n ≈ 2 ln n: P(2) = 1, P(3) = 8/3, and for n = 100 the average depth is 6.48 (a seeded 2000-tree simulation agrees within 3%) versus 2 ln 100 = 9.21.

(3) The Yn = 2Xn recurrence. E[Yn] ≤ (4/n)·Σi=0n−1 E[Yi] with E[Y0] = 0, E[Y1] = 1. Induction using Σi=0n−1 C(i+3, 3) = C(n+3, 4) gives E[Yn] ≤ C(n+3, 3)/4 = O(n³); Jensen then gives E[Xn] ≤ lg(C(n+3, 3)/4) ≈ 3 lg n (15.43 for n = 100). The code iterates the recurrence for n ≤ 600, checks the cubic bound and the binomial identity, and checks Jensen on simulated heights.

Quiz

Interview questions

Cheat sheet