TAOCP Vol 4A: Combinatorial Algorithms, Part 1 · Week 114
TAOCP 7.2.1.6 Generating All Trees: reading guide
Generating all binary trees, forests and nested parenthesis strings, and the Catalan number connections between them, with efficient (often loopless) algorithms.
Time About 8 hours this week
Why it matters
Generating all trees is useful for testing tree code exhaustively (a great way to find bugs in an AVL or parser). The Catalan connections tie back to 2.3.4.
Before you start
- 2.3.4 Mathematical properties of trees
- 7.2.1.5
How to approach it
Implement nested parentheses generation and convert each string to a binary tree. Use it to exhaustively test one of your tree implementations from Vol 3.
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.