Chapter 11
Advanced Tree Algorithms
Two structural ideas carry this whole chapter: sort-and-merge (MST, Kruskal) and split-at-a-good-vertex (centroid, HLD). Everything else is bookkeeping.
6 pages5,298 words16 problems3 interactive
1Minimum Spanning TreeKruskal, Prim, and Borůvka from one lemma; the cut property, the exchange argument, and what each algorithm is actually for.2Small-to-Large MergingWhy merging the smaller container into the larger one gives O(n log n) total work, and the dozen problems where that one line is the whole solution.3Centroid DecompositionThe divide-and-conquer that turns "count pairs at distance d" into O(n log n) — plus the centroid itself, proved, and the traps that make implementations slow.4Heavy-Light DecompositionPath queries with updates in O(log^2 n) — the decomposition, why light edges are few, the segment tree layout, and lazy propagation on chains.5Tree Hashing and IsomorphismA canonical form for unordered rooted trees, a randomised hash that is one line, and the collision you must not ignore.6Huffman CodingGreedy tree-building for optimal prefix codes, the sibling property, and the same algorithm hiding in "merge stones", "minimum cost tree", and optimal alphabetic coding.