TAOCP 2.3.1 Exercise 18

Section 2.3.1: Traversing Binary Trees

Exercise 18. [24] Many algorithms dealing with trees like to visit each node twice instead of once, using a combination of preorder and inorder that we might call double order. Traversal of a binary tree in double order is defined as follows: If the binary tree is empty, do nothing; otherwise

a) visit the root, for the first time;
b) traverse the left subtree, in double order;
c) visit the root, for the second time;
d) traverse the right subtree, in double order.

For example, traversal of (1) in double order gives the sequence

$$ A_1 B_1 D_1 D_2 B_2 A_2 C_1 E_1 E_2 G_1 G_2 C_2 F_1 H_1 H_2 F_2 J_1 J_2, $$

where A_1 means that A is being visited for the first time.

If P points to a node of the tree and if d = 1 or 2, define (P, d)^\Delta = (Q, e) if the next step in double order after visiting NODE(P) the dth time is to visit NODE(Q) the eth time; or, if (P, d) is the last step in double order, we write (P, d)^\Delta = (HEAD, 2), where HEAD is the address of the list head. We also define (HEAD, 1)^\Delta as the first step in double order.

Design an algorithm analogous to Algorithm T that traverses a binary tree in double order, and also design an algorithm analogous to Algorithm S that computes (P, d)^\Delta. Discuss the relation between these algorithms and exercises 12 and 17.

Verified: no
Solve time: 53s

---

Solution

The double-order traversal visits each node twice. The first visit occurs at the position occupied by the root in preorder; the second visit occurs at the position occupied by the root in inorder. Therefore a traversal algorithm analogous to Algorithm T must distinguish between these two kinds of visits.

Let the auxiliary stack A contain pairs (P,d), where d=1 means that NODE(P) has been visited the first time but not yet the second time.

Algorithm D (Traverse binary tree in double order)

Let T be a pointer to a binary tree represented as in (2).

D1. [Initialize.] Set stack A empty, and set P \leftarrow T.

D2. [P = \Lambda?] If P=\Lambda, go to step D5.

D3. [Visit first time.] Visit NODE(P) for the first time. Set A \leftarrow (P,1).

D4. [Go left.] Set P \leftarrow LLINK(P) and return to step D2.

D5. [Stack empty?] If stack A is empty, terminate. Otherwise set (P,d)\leftarrow A.

D6. [Visit second time.] Visit NODE(P) for the second time.

D7. [Go right.] Set P \leftarrow RLINK(P) and return to step D2. ∎

To verify correctness, consider entry into step D2 with P pointing to a subtree rooted at P_0. Step D3 performs part (a) of the definition of double order, namely the first visit to the root. The pair (P_0,1) is retained on the stack while the left subtree is traversed. When the traversal of the left subtree is complete, step D5 restores P_0; step D6 performs part (c), namely the second visit to the root. Step D7 then initiates traversal of the right subtree, which is part (d). Thus the order of actions is exactly

$$ \text{root}_1,\quad \text{left subtree},\quad \text{root}_2,\quad \text{right subtree}, $$

which is the recursive definition of double order.

The successor operation $(P,d)^\Delta$ can be computed most naturally in a threaded tree. Since the first visit corresponds to preorder and the second visit corresponds to inorder, the successor rule is obtained by combining the ideas of exercises 12 and 17.

Assume a threaded binary tree with list head HEAD as in (8), (9), and (10).

Algorithm \Delta (Double-order successor)

Given (P,d), this algorithm sets (Q,e)\leftarrow(P,d)^\Delta.

\Delta1. [First visit?] If d=1, go to step \Delta2; otherwise go to step \Delta5.

\Delta2. [Left child exists?] If LTAG(P)=0, set Q\leftarrow LLINK(P), e\leftarrow1, and terminate.

\Delta3. [No left child.] Set Q\leftarrow P, e\leftarrow2, and terminate.

\Delta5. [Second visit.] If RTAG(P)=0, set Q\leftarrow RLINK(P), e\leftarrow1, and terminate.

\Delta6. [Move upward.] Set Q\leftarrow RLINK(P).

\Delta7. [End of traversal?] If Q=\text{HEAD}, set e\leftarrow2 and terminate.

\Delta8. [Came from left?] If LTAG(Q)=0 and LLINK(Q)=P, set e\leftarrow2 and terminate.

\Delta9. [Continue upward.] Set P\leftarrow Q and return to step \Delta6. ∎

The correctness follows directly from the definition of double order.

If d=1, the next action after the first visit to a node is either the first visit to the root of its left subtree, if that subtree exists, or the second visit to the node itself if the left subtree is empty. Steps \Delta2 and \Delta3 implement these two possibilities.

If d=2, the next action is either the first visit to the root of the right subtree, if that subtree exists, or else an ascent toward the first ancestor whose left subtree has just been completed. At that ancestor the next event is the ancestor's second visit. Steps \Delta5 through \Delta9 implement precisely this search. The ascent rule is identical to the intuitive description of inorder succession in exercise 16, except that arrival at the appropriate ancestor produces the second visit of that ancestor rather than an inorder successor.

The relation to exercises 12 and 17 is immediate. The first visits in double order form the preorder sequence exactly; hence the transitions among first visits are governed by the preorder-successor mechanism of exercises 12 and 17. The second visits in double order occur in inorder; hence the transitions among second visits are governed by the inorder-successor mechanism embodied in Algorithm S. Double order may therefore be regarded as an interleaving of preorder and inorder traversals, with each node appearing once in each order. The traversal algorithm D is obtained from the preorder traversal algorithm of exercise 12 by inserting a second visit when the node is recovered after traversal of its left subtree, and the successor algorithm \Delta is obtained by combining the preorder and inorder successor rules into a single state space consisting of pairs (P,1) and (P,2).

The final state is

$$ (\text{HEAD},1)^\Delta = (\text{root},1), \qquad (P,d)^\Delta = (\text{HEAD},2) $$

for the last double-order visit (P,d).

$$ \boxed{\text{Algorithms D and }\Delta\text{ above traverse and generate double order.}} $$