TAOCP 6.2.2 Exercise 44
Phase 3 of the Garsia-Wachs algorithm constructs the optimal binary tree from the leaf levels \(l_0, l_1, \ldots, l_n\) (where \(l_i\) is the level of the \(i\)th leaf in symmetric order, with the roo...
Section 6.2.2: Binary Tree Searching
Exercise 44. [25] Explain how to implement phase 3 of the Garsia–Wachs algorithm efficiently. Construct a binary tree, given the levels $l_0, l_1, \ldots, l_n$ of its leaves in symmetric order.
Verified: no
Solve time: 1m45s
Solution
Phase 3 of the Garsia-Wachs algorithm constructs the optimal binary tree from the leaf levels (l_0, l_1, \ldots, l_n) (where (l_i) is the level of the (i)th leaf in symmetric order, with the root at level (0)). The tree is uniquely determined by these levels because the leaves appear in symmetric order and every internal node has exactly two children.
We use a stack to build the tree bottom‑up. Each stack entry is a pair ((P, d)) where (P) points to the root of a subtree and (d) is the level of that root. The algorithm processes the leaves from left to right, combining subtrees whenever two adjacent ones have the same level.
Algorithm G (Phase 3 - construct tree from leaf levels).
G1. [Initialize.] Set the stack to empty.
G2. [Loop over leaves.] For (i = 0, 1, \ldots, n) do steps G3, G4, G5.
G3. [Create leaf.] Allocate a new node (Q) for leaf (i); set (\text{LLINK}(Q) \leftarrow \text{RLINK}(Q) \leftarrow \Lambda). Set (d \leftarrow l_i).
G4. [Combine equal levels.] While the stack is not empty and the level of the top entry equals (d): Pop the top entry ((R, d)) from the stack. Create a new internal node (S); set (\text{LLINK}(S) \leftarrow R), (\text{RLINK}(S) \leftarrow Q). Set (Q \leftarrow S) and (d \leftarrow d - 1).
G5. [Push combined subtree.] Push ((Q, d)) onto the stack.
G6. [Finish.] After the loop, the stack contains exactly one entry ((T, 0)). The desired tree is rooted at (T).
Correctness. We prove by induction on (i) that after processing leaves (0,\ldots,i) the stack from bottom to top holds the roots of a sequence of subtrees that
- together contain exactly leaves (0,\ldots,i) in symmetric order,
- have strictly increasing levels, and
- are the maximal subtrees that are completely determined by the leaves seen so far (i.e., no two adjacent subtrees on the stack can be siblings in the final tree).
For (i=0) the stack contains the single leaf (0) at level (l_0), so the properties hold. Assume they hold after (i) leaves. When leaf (i+1) is added (step G3), it starts as a subtree of level (l_{i+1}). Step G4 repeatedly checks whether the rightmost subtree on the stack has the same level as the current subtree. If so, they must be siblings in the final tree, because two adjacent subtrees whose roots are at the same level can only be children of a common parent at level one less. The loop creates that parent and continues upward as long as the new parent again meets a subtree of the same level. This exactly mirrors the structure of the unique binary tree with the given leaf levels. After the loop, the current subtree has a level strictly smaller than the level of the new top (or the stack is empty), so pushing it preserves the strictly increasing order of levels. The new sequence of subtrees covers leaves (0,\ldots,i+1) and is maximal, completing the induction.
At termination, all (n+1) leaves are covered. The sum of (2^{-l_i}) over all leaves equals (1) (Kraft equality), which forces the final stack to contain exactly one subtree whose level is (0) - the root of the whole tree.
Efficiency. Each leaf is pushed once and popped at most once; each internal node is created once and pushed/popped at most once. Hence the total number of stack operations is (O(n)), and the algorithm runs in (O(n)) time with (O(n)) auxiliary space (the stack depth never exceeds (\max_i l_i \le n)).
This completes the proof. ∎