TAOCP 2.3.1 Exercise 20
Algorithm `T` uses an auxiliary stack `A` in consecutive memory locations.
Section 2.3.1: Traversing Binary Trees
Exercise 20. [23] Modify Program T so that it keeps the stack in a linked list, not in consecutive memory locations.
Verified: no
Solve time: 33s
Solution
Algorithm T uses an auxiliary stack A in consecutive memory locations. To keep the stack in a linked list, replace the stack representation by nodes containing two fields:
$$ \text{INFO}(X),\quad \text{LINK}(X), $$
where INFO(X) contains a saved pointer value and LINK(X) points to the next stack element. Let A be a pointer to the top of the stack; thus A = \Lambda means that the stack is empty.
The push operation in step T3 must create a new stack node and link it to the former stack top. The pop operation in step T4 must recover the saved pointer and remove the top stack node. Preserving the notation of Algorithm T as closely as possible, we obtain:
Algorithm T′ (Traverse binary tree in inorder, linked stack).
T1. [Initialize.] Set A \leftarrow \Lambda, and set the link variable P \leftarrow T.
T2. [P = Λ?] If P = \Lambda, go to step T4.
T3. [Stack ← P.] Set Q \leftarrow \text{AVAIL}; \text{AVAIL} \leftarrow \text{LINK}(Q). Set \text{INFO}(Q) \leftarrow P, \text{LINK}(Q) \leftarrow A, A \leftarrow Q. Then set P \leftarrow \text{LLINK}(P) and return to step T2.
T4. [P ← Stack.] If A = \Lambda, terminate the algorithm. Otherwise set Q \leftarrow A, A \leftarrow \text{LINK}(Q), P \leftarrow \text{INFO}(Q), \text{LINK}(Q) \leftarrow \text{AVAIL}, \text{AVAIL} \leftarrow Q.
T5. [Visit P.] Visit NODE(P). Then set P \leftarrow \text{RLINK}(P) and return to step T2. ∎