TAOCP 2.3.3 Exercise 2

Section 2.3.3: Other Representations of Trees

Exercise 2. [22] (Burks, Warren, and Wright, Math. Comp. 8 (1954), 53-57.) The trees (2) stored in preorder with degrees would be

$$ \begin{array}{c|cccccccccc} \text{DEGREE} & 2 & 0 & 1 & 0 & 3 & 1 & 0 & 1 & 0 & 0\ \text{INFO} & A & B & C & K & D & E & H & F & J & G \end{array} $$

[compare with (9), where postorder was used]. Design an algorithm analogous to Algorithm F to evaluate a locally defined function of the nodes by going from right to left in this representation.

Verified: no
Solve time: 38s

Solution

We are asked to design an algorithm analogous to Algorithm F for the preorder with degrees representation of a forest, traversing from right to left. Let the forest be represented as

$$ \begin{array}{c|cccccccccc} \text{DEGREE} & d_1 & d_2 & \dots & d_n\ \text{INFO} & x_1 & x_2 & \dots & x_n \end{array} $$

with the nodes listed in preorder and DEGREE(P) giving the number of children of NODE(P). Denote by $n$ the total number of nodes. In preorder, each node appears before its children, so the children of NODE(P) occupy the positions immediately following P in the array. Since we scan from right to left, the children of a node have already been processed when we reach the node itself, just as in Algorithm F where the stack holds child values.

Let S be a stack storing computed values of f for nodes. The invariant is: at any point, the top of the stack corresponds to the rightmost child not yet combined for the current ancestor node.

Algorithm G. [Evaluate a locally defined function in a preorder with degrees forest, scanning right to left.]

G1. [Initialize.] Set the stack S empty, and let P point to the last node of the forest in the array (rightmost node in preorder).

G2. [Evaluate f.] Let d <- DEGREE(P). Then the top d items of the stack are the values $f(x_1), \dots, f(x_d)$ corresponding to the children of NODE(P) from left to right, since in preorder the children occupy consecutive positions after the node itself. Evaluate

$$ f(NODE(P)) \quad \text{using these $d$ child values from left to right.} $$

G3. [Update the stack.] Remove the top d items of S (corresponding to the children) and push f(NODE(P)) onto the stack.

G4. [Advance.] If P is the first node in the array, terminate. Otherwise, set P \leftarrow P - 1 and return to step G2.

Correctness. We prove the correctness by induction on the number of nodes remaining to the left of P. For the rightmost node (base case), d = 0 and the stack is empty, so f(NODE(P)) is correctly evaluated and pushed. Assume that for all nodes strictly to the right of P, the stack invariant holds. When processing NODE(P), the d children are exactly the next d nodes to the right in preorder, which have already been processed and whose values reside on top of the stack. Removing these d values and pushing f(NODE(P)) correctly maintains the invariant. By induction, after the leftmost node is processed, the stack contains f(root(T_m)), \dots, f(root(T_1)) from top to bottom, where $T_1, \dots, T_m$ are the trees of the forest. This completes the proof. ∎

Remarks.

1. The preorder property ensures that children appear consecutively after their parent, allowing right-to-left scanning to process all children before the parent.
2. The stack always holds exactly the computed values of uncombined child nodes for the next ancestor to be processed.
3. The algorithm is identical in spirit to Algorithm F, differing only in the scanning order and the fact that the number of children is obtained from DEGREE(P) rather than counting nodes in postorder.

The algorithm is compact and requires exactly one evaluation of f per node and one push/pop operation per child, which mirrors the operation count in Algorithm F.