Week 41 of 125
TAOCP 2.3.3 Other Representations of Trees
Sign up or sign in to tick these off and give this week a due date.
-
Alternative ways to store trees: sequential layouts using preorder with degrees, parent links only, and more. It includes the algorithm for processing equivalence relations by keeping trees with parent pointers, the ancestor of union-find.
Time About 7 hours this week
Why it matters
Union-find is a workhorse (Kruskal's algorithm, connected components, type inference). Compact tree encodings matter for serialization and succinct data structures.
Before you start
- 2.3.2 Binary Tree Representation of Trees
How to approach it
Implement the equivalence algorithm with parent pointers, then add path compression and union by size yourself and measure the speedup. The sequential representations are quick reads.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Forgetting to find the roots before linking two trees.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.