TAOCP 2.3.1 Exercise 22

Section 2.3.1: Traversing Binary Trees

Exercise 22. [25] Write a MIX program for the algorithm given in exercise 21 and compare its execution time to Programs S and T.

Verified: no
Solve time: 36s

Solution

We are asked to write a MIX program that implements the algorithm of Exercise 21, which traverses an unthreaded binary tree in inorder without using any auxiliary stack, modifying the LLINK and RLINK fields temporarily but restoring the tree to its original structure afterward. This algorithm is the Morris traversal described in Section 2.3.1, which exploits temporary right links from a node's inorder predecessor to the node itself.

Let T be the pointer to the root of the tree. Each node P has fields LLINK(P) and RLINK(P) pointing to the left and right children, and NODE(P) containing the data. The algorithm proceeds as follows in pseudocode before translation to MIX:

Algorithm M (Inorder traversal without stack):

Set P <- T.
While P ≠ Λ do:
If LLINK(P) = Λ, then
Visit NODE(P).
Set P <- RLINK(P).
Else
Let Q <- LLINK(P).
While RLINK(Q) ≠ Λ and RLINK(Q) ≠ P do Q <- RLINK(Q).
If RLINK(Q) = Λ, then
Set RLINK(Q) <- P.
Set P <- LLINK(P).
Else
Set RLINK(Q) <- Λ.
Visit NODE(P).
Set P <- RLINK(P).

This algorithm visits each node exactly once in inorder, uses only temporary modifications of RLINK pointers, and restores the original tree. Each assignment counts as one replacement in Knuth's sense.

MIX Program

We assume the following conventions:

Memory locations are used to store nodes in consecutive words.
Each node occupies 3 words: LLINK, NODE, RLINK.
T is stored in location 1000.
Registers: A for temporary data, I for indexing, J for traversal pointers, P for current node, Q for predecessor.
Subroutines VISIT outputs NODE(P).

* Morris inorder traversal in MIX
        ORIG    2000
P       EQU     2000            * current node pointer
Q       EQU     2001            * predecessor pointer
T       EQU     1000            * root pointer

        LDA     T,0             * P <- T
NEXT    CMPA    =0=             * check P = Λ
        JEQ     DONE

        LDX     P,0             * X <- LLINK(P)
        CMPX    =0=
        JEQ     VISIT_NODE

        STX     Q               * Q <- LLINK(P)
FIND_PRE
        LDA     Q+2,0           * load RLINK(Q)
        CMPA    =0=
        JEQ     SET_THREAD
        CMPA    P,0
        JEQ     REMOVE_THREAD
        TIX     Q,2
        JMP     FIND_PRE

SET_THREAD
        STA     Q+2,0           * RLINK(Q) <- P
        LDX     P,0             * P <- LLINK(P)
        JMP     NEXT

REMOVE_THREAD
        LDA     =0=             * RLINK(Q) <- Λ
        STA     Q+2,0
VISIT_NODE
        LDA     P+1,0           * load NODE(P)
        JSUB    VISIT
        LDX     P+2,0           * P <- RLINK(P)
        JMP     NEXT

DONE    HLT

VISIT   ...                     * subroutine to process NODE(P)
        JMP     NEXT

Execution-Time Comparison

Let $n$ be the number of nodes:

Program T (Algorithm T with a stack) executes $2n$ pointer traversals plus $n$ stack pushes and $n$ stack pops.
Program S (Algorithm S, threaded trees) executes roughly one pointer traversal per node plus some iterations along left links; if the tree is balanced, the total number of steps is $O(n)$.
Program M (Morris traversal) executes at most $2n$ traversals of RLINK pointers plus $n$ visits and temporary assignments. Each node is visited at most twice (once to find predecessor, once after restoring links). Therefore, the number of MIX instructions is comparable to Program T, but no auxiliary memory is needed. For trees with long left chains, the inner loop may execute up to $n-1$ times for a single node, giving a worst-case execution time of $O(n^2)$, but the average running time on a random node of a balanced tree is $O(n)$.

This completes the solution. ∎