Optimal Binary Search Tree, in depth: the interval DP, Knuth's root window and a fully worked example

The cost model: hits, misses and depth

Take sorted keys k1 through kn. Each key ki has a weight p[i], the number (or probability) of successful searches for it. Between and around the keys sit n+1 gaps d0 through dn: d0 holds every query smaller than k1, di every query strictly between ki and ki+1, and dn every query larger than kn. Each gap has a weight q[i], the unsuccessful searches that end there. In the tree the gaps are the empty child pointers, drawn as dummy leaves.

The cost of a tree is the sum over all keys of p[i] times the number of nodes visited to reach ki, plus the sum over all gaps of q[i] times the number of steps to fall off the tree at that gap. With the root at depth 0, a key at depth d costs d+1 and a dummy leaf at depth d also costs d+1, which is the convention in Cormen et al. and the one used throughout this article. Divide by the total weight to get the expected cost per lookup.

Misses are not optional: an identifier table may see more misses than hits, and ignoring q tunes the tree for the wrong traffic. Weights can be raw counts instead of probabilities, which keeps the arithmetic exact.

Why greedy and balanced trees lose

The worked example uses five keys, apply, bind, cast, drop and emit, with hit counts p = 15, 12, 2, 10, 8 and miss counts q = 0, 0, 2, 1, 0, 0 for gaps d0 to d5. The total weight is 50 lookups.

Heuristic one: put the most frequent key at the root and recurse. That chooses apply (15). Every other key now sits in the right subtree, one level deeper, and the tree costs 124. Heuristic two: ignore frequencies and balance by position. That chooses cast, the median key, which has weight 2, and the tree costs 123. The optimum is 104, about 15 percent cheaper than either, and its root is bind, neither the most frequent key nor the median.

The reason is that the root's own weight is paid once, but the root also decides how much weight is pushed one level down on each side. bind splits the 50 units of traffic into 15 on the left and 23 on the right while keeping 12 at depth 0. A good root is a compromise between being heavy and splitting the rest evenly, and no local rule captures that trade reliably. Dynamic programming does.

Optimal substructure and the recurrence

Every subtree of a BST holds a contiguous range of keys ki to kj together with gaps d(i-1) to dj. If the whole tree is optimal, every subtree must be optimal for its range: swapping in a cheaper subtree would lower the total, because the subtree's contribution depends only on its own shape plus a constant shift for its depth. That is optimal substructure over intervals.

Define w(i, j) as the total weight of the range, the sum of p[i..j] and q[i-1..j]. Define e(i, j) as the minimum cost of a tree for that range. When a subtree is hung one level deeper, every node in it costs one more visit, so its cost rises by exactly its weight. Choosing root r for range i..j therefore gives:

e(i, i-1) = q[i-1]                               # empty range: just the gap
w(i, j)   = w(i, j-1) + p[j] + q[j]
e(i, j)   = w(i, j) + min over i <= r <= j of ( e(i, r-1) + e(r+1, j) )
root(i, j) = the r that achieves the minimum

The w(i, j) term accounts for the root and the one-level push of both subtrees in a single addition. Ranges are solved in order of increasing length so that both sub-ranges are ready when a longer range needs them. There are O(n squared) ranges and each tries O(n) roots, so the straightforward algorithm takes O(n cubed) time and O(n squared) memory.

The cubic algorithm in code

The implementation below uses 1-based keys so the indices match the recurrence; p[0] is unused. It returns the minimum cost and the root table, which is all you need to rebuild the tree.

def optimal_bst(p, q):
    # p[1..n]: hit weights (p[0] unused); q[0..n]: miss weights.
    n = len(p) - 1
    e = [[0] * (n + 1) for _ in range(n + 2)]
    w = [[0] * (n + 1) for _ in range(n + 2)]
    root = [[0] * (n + 1) for _ in range(n + 2)]
    for i in range(1, n + 2):
        e[i][i - 1] = w[i][i - 1] = q[i - 1]
    for length in range(1, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            w[i][j] = w[i][j - 1] + p[j] + q[j]
            e[i][j] = float("inf")
            for r in range(i, j + 1):
                t = e[i][r - 1] + e[r + 1][j] + w[i][j]
                if t < e[i][j]:
                    e[i][j], root[i][j] = t, r
    return e[1][n], root


def build(root, keys, i, j):
    # keys is 1-based like p; returns (key, left, right) tuples, None for a gap.
    if i > j:
        return None
    r = root[i][j]
    return (keys[r], build(root, keys, i, r - 1), build(root, keys, r + 1, j))


keys = [None, "apply", "bind", "cast", "drop", "emit"]
cost, root = optimal_bst([0, 15, 12, 2, 10, 8], [0, 0, 2, 1, 0, 0])
print(cost)                       # 104
print(build(root, keys, 1, 5))    # ('bind', ('apply', None, None), ('drop', ...))

Worked example: the full table

The table lists every range of two or more keys, shortest first. The candidates column shows the cost for each possible root so you can check the minimum by hand.

Single-key ranges are simple: e(1,1) = 15 for apply alone with empty gaps, e(3,3) = 8 for cast with its gap weights 2 and 1 pushed one level down. Trace the final row: choosing bind costs e(1,1) + e(3,5) + w(1,5) = 15 + 39 + 50 = 104. Reading the root table top-down gives bind at the root, apply on the left, drop on the right with cast and emit below it. On average a lookup visits 104 / 50 = 2.08 nodes.

Knuth's root window: from cubic to quadratic

Knuth showed in 1971 that the optimal roots are monotone: some optimal root of range i..j lies between an optimal root of i..j-1 and an optimal root of i+1..j. Intuitively, adding a key on the right can only pull the best split rightwards, and removing a key on the left cannot pull it leftwards. In the table, root(1,4) is bind (2) and root(2,5) is drop (4), so root(1,5) only needs candidates 2 to 4, and the answer, 2, is inside the window.

Restricting the inner loop to that window changes the total work. For a fixed length L, the window sizes are root(i+1, j) - root(i, j-1) + 1, and summing over i telescopes to at most n plus the number of ranges, so each length costs O(n) and the whole table O(n squared). The change is two lines:

            lo = root[i][j - 1] if j > i else i
            hi = root[i + 1][j] if j > i else i
            for r in range(lo, hi + 1):          # was: range(i, j + 1)

The window is only valid if the tables it reads were filled with consistent choices, and tie-breaking matters when several roots give the same cost. Taking the first minimum, as above, is safe. The guarantee is about the cost: the restricted search still finds the optimal e(1, n). Do not trust that argument blindly in your own variant; check it. On 500 random instances with up to nine keys and integer weights, the cubic and windowed versions agreed on every optimal cost.

Larger inputs and approximate trees

Quadratic time and memory are fine for thousands of keys and painful for millions. Three alternatives exist. If only the leaves carry weight, as in alphabetic prefix codes, the Hu-Tucker and Garsia-Wachs algorithms build the optimal alphabetic tree in O(n log n). If near-optimal is enough, Mehlhorn's approximation picks the root that best balances weight on each side, recurses, and runs in roughly O(n log n) or better, with a cost bound close to the entropy of the access distribution. And if the frequencies are not known in advance or drift, a splay tree adapts on its own: its static optimality theorem says that over a long access sequence it is within a constant factor of the best static tree, without being told the frequencies. And if your weights are nearly uniform, the optimum is close to a balanced tree and the DP buys almost nothing.

When to use it in production

The optimal BST is a static structure. It pays off when the key set is fixed, the access distribution is measured and stable, and comparisons are expensive enough to matter, for example string comparisons over long shared prefixes, or decision trees generated for a switch over sparse values. Compilers and lexers often reach for a perfect hash instead, which is O(1) per lookup and does not need frequencies; choose the BST when you also need ordered operations such as predecessor, range scans or prefix queries.

Collect frequencies, including misses, from production traffic rather than guesses, and version them with the tree. Rebuild offline, compare expected cost against the current tree on recent traffic, and ship only past a margin chosen in advance. Store the result as a flat array or nested switch so there are no pointers to chase.

Failure modes

The bugs and failure modes that show up in real implementations:

• Off-by-one in the gap indices. Range i..j owns gaps i-1 through j. Getting that wrong shifts every miss weight by one gap, and the result still looks plausible.
• Forgetting the empty ranges. e(i, i-1) must be q[i-1], not 0, or misses vanish from the cost.
• Recomputing w inside the loop. Correct but O(n to the fourth); profile before blaming Python.
• Floating-point ties. Rounded probabilities make the chosen root flip; use integer counts.
• Stale weights. A tree tuned for last quarter's traffic can be worse than a balanced tree for this quarter's. Monitor the realised average depth.

Testing the implementation

Test the DP against brute force. For n up to about eight, enumerate every root recursively and compare costs; the number of trees is a Catalan number, so stop before n gets large.

import random

def brute(p, q, i, j, depth=1):
    if i > j:
        return q[i - 1] * depth
    return min(p[r] * depth + brute(p, q, i, r - 1, depth + 1)
               + brute(p, q, r + 1, j, depth + 1) for r in range(i, j + 1))

for _ in range(300):
    n = random.randint(1, 7)
    p = [0] + [random.randint(0, 20) for _ in range(n)]
    q = [random.randint(0, 20) for _ in range(n + 1)]
    assert optimal_bst(p, q)[0] == brute(p, q, 1, n)

Add property checks as well: an in-order walk of the rebuilt tree must return the keys sorted; uniform weights must give the cost of a balanced tree; and the cubic and Knuth versions must agree on every random case.

Related reading

To keep learning, start with BST operations in depth for the search, insert and delete mechanics this cost model is built on, then dynamic programming fundamentals for the general method. Huffman coding solves the close cousin where key order does not matter, and greedy is optimal there. For self-adjusting alternatives read treaps, and for order statistics on any BST see finding the k-th smallest element.

What to do next

1. Run the code above on the five-key example and confirm the cost 104 and the root bind.
2. Change one weight, for example raise cast to 20, predict the new root, then check.
3. Add the two-line Knuth window and verify it against the cubic version and the brute-force tester.
4. Collect real hit and miss counts for one static lookup table in your code base.
5. Compute the realised average depth of your current structure against the optimum before deciding to switch.
6. If you switch, version the weights, rebuild offline, and alert when realised depth drifts from the prediction.