TAOCP 2.3.1 Exercise 13

A postorder traversal must process a node only after both of its subtrees have been traversed.

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.1: Traversing Binary Trees

Exercise 13. [24] Design an algorithm analogous to Algorithm T that traverses a binary tree in postorder.

Verified: no
Solve time: 48s

Solution

A postorder traversal must process a node only after both of its subtrees have been traversed. In Algorithm T, when a node is removed from the stack, the left subtree has already been traversed, but the right subtree has not. Therefore a second state must be remembered for each node, indicating whether its right subtree has already been traversed.

Let stack A contain pairs (P,i), where i=0 means that the left subtree of P has not yet been traversed, and i=1 means that the left subtree has been traversed but the right subtree has not.

Algorithm P (Traverse binary tree in postorder)

Let T be a pointer to a binary tree represented as in (2). This algorithm visits all nodes in postorder.

P1. [Initialize.] Set stack A empty, and set P <- T.

P2. [P = Λ?] If P = \Lambda, go to step P4.

P3. [Stack ← (P,0).] Set A <- (P,0). Then set P <- LLINK(P) and return to step P2.

P4. [Stack empty?] If stack A is empty, the algorithm terminates; otherwise set (P,i) <- A.

P5. [Left subtree done?] If i=0, set A <- (P,1), set P <- RLINK(P), and return to step P2.

P6. [Visit P.] Visit NODE(P). Set P <- \Lambda and return to step P4. ∎

We prove correctness by induction on the number of nodes.

Consider the following statement:

Starting at step P2 with P a pointer to a binary tree of n nodes and with stack A containing some initial contents, the procedure of steps P2-P6 traverses that binary tree in postorder and ultimately arrives at step P4 with stack A restored to its original contents.

When n=0, we have P=\Lambda. Step P2 transfers control immediately to step P4; no nodes are visited and the stack is unchanged. Thus the statement holds.

Assume the statement holds for all binary trees having fewer than n nodes, where n>0. Let P_0 be the value of P upon entry to step P2.

Since P_0\ne\Lambda, steps P2-P3 place (P_0,0) on the stack and set

$$ P \leftarrow LLINK(P_0). $$

The left subtree of P_0 contains fewer than n nodes. By the induction hypothesis, execution returns to step P4 with stack contents restored except for the presence of (P_0,0).

Step P4 removes (P_0,0) from the stack and sets (P,i)=(P_0,0). Step P5 replaces this by (P_0,1) and sets

$$ P \leftarrow RLINK(P_0). $$

The right subtree of P_0 also contains fewer than n nodes. By the induction hypothesis, execution returns to step P4 with the stack restored except for the presence of (P_0,1).

Step P4 removes (P_0,1) from the stack and sets (P,i)=(P_0,1). Step P5 is bypassed, and step P6 visits NODE(P_0).

Thus the operations occur in the order

  1. Traverse the left subtree of P_0.
  2. Traverse the right subtree of P_0.
  3. Visit NODE(P_0).

This is exactly the recursive definition of postorder traversal. After step P6, the pair corresponding to P_0 has been removed permanently, so the stack is restored to its original contents. Therefore the induction statement holds for trees of n nodes.

By induction, Algorithm P traverses every binary tree in postorder and terminates after visiting each node exactly once.

This completes the proof.

∎