Hu-Tucker Algorithm

Purpose: Build an optimal alphabetic binary tree in $O(n\log n)$ — the minimum-cost binary tree over $n$ weighted leaves where the leaves must appear in their original left-to-right order.

Hu-Tucker vs Huffman

	Huffman	Hu-Tucker
Leaf order	free — reorder as you like	fixed
Method	repeatedly merge the two smallest	three-phase, order-respecting
Time	$O(n\log n)$	$O(n\log n)$
Use	data compression	ordered search trees, alphabetic codes

The constraint changes everything. Huffman’s greedy “merge the two smallest” is invalid here, because the two smallest weights may not be adjacent, and merging them would reorder the leaves.

Algorithm (three phases)

1. Combination. Repeatedly merge the pair of nodes $(i,j)$ with minimum $w_i+w_j$ among all pairs that are “tentatively adjacent” — meaning every node strictly between them has already been merged away. Ties are broken by leftmost position. Record the level each original leaf ends up at. This phase does not build the final tree; it only determines the depths.
2. Level assignment. Read off ${\ell }_i$, the depth of leaf $i$ in the combination tree.
3. Reconstruction. Rebuild a tree with the leaves in their original order and the depths ${\ell }_i$ found in phase 1. Such a tree always exists (the depths satisfy the Kraft equality) and is optimal.

The surprising theorem is that the depths from the unconstrained-looking phase 1 are exactly realisable in order — this is the whole content of the Hu-Tucker result and its proof is not short.

Complexity

• Time: $O(n\log n)$ with a priority queue over tentatively-adjacent pairs
• Space: $O(n)$

Alternatives

Approach	Time	Optimal?
Interval DP $dp[i][j]$	$O(n^3)$	yes
Interval DP + Knuth optimization	$O(n^2)$	yes
Hu-Tucker	$O(n\log n)$	yes
Garsia-Wachs	$O(n\log n)$	yes — simpler to implement
Mehlhorn’s greedy heuristic	$O(n)$	within 2 bits of optimal

Garsia-Wachs

If you ever need this in practice, implement Garsia-Wachs instead: it is a cleaner reformulation of the same three-phase idea, with a much shorter description and the same $O(n\log n)$ bound. The typical contest version of this problem (merging adjacent piles of stones with cost = sum) is usually small enough for $O(n^2)$ Knuth optimization anyway.

Applications

• Optimal alphabetic codes — prefix codes where the code order must match the symbol order (so that comparing codes compares symbols)
• Optimal binary search trees with only successful searches — closely related; Knuth’s $O(n^2)$ algorithm is the standard solution
• Merging ordered files / piles of stones — the recurring contest form: merge adjacent piles, cost = combined size, minimise total
• Circuit design and code trees where physical ordering is fixed

Variants / Use Cases

• Huffman Coding — the unordered version
• Knuth Optimization — the $O(n^2)$ DP route
• Scheduling — where exchange-argument greedy proofs live
• Interval DP — the general framework for this problem shape