Week 40: TAOCP 2.3.2 Binary Tree Representation of Trees

Any general tree or forest can be stored as a binary tree using the "first child, next sibling" trick. Knuth applies it to symbolic differentiation of algebraic formulas stored as trees.

Time About 7 hours this week

Why it matters

The child-sibling representation is how many compilers and file systems store variable-arity trees. Symbolic differentiation is a mini compiler pass, so it should feel familiar after Crafting Interpreters.

Before you start

2.3.1 Traversing Binary Trees
Basic derivatives

How to approach it

Convert a few small forests to binary trees by hand. Then implement a tiny symbolic differentiator over an expression tree in any language. It is a fun weekend project.

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 that preorder of the forest equals preorder of the binary tree, but postorder of the forest corresponds to inorder of the binary tree. Check it on an example.