TAOCP 2.3.1 Exercise 30

Let `T` be an unthreaded binary tree, represented in the standard form of (2), and let `P` be a pointer to a node of `T`.

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.1: Traversing Binary Trees

Exercise 30. [22] Design an algorithm that threads an unthreaded tree; for example, it should transform (2) into (10). Note: Always use notations like P* and P$ when possible, instead of repeating the steps for traversal algorithms like Algorithm T.

Verified: yes
Solve time: 1m13s

Solution

Let T be an unthreaded binary tree, represented in the standard form of (2), and let P be a pointer to a node of T. The goal is to construct a procedure that converts T into a threaded binary tree, that is, to assign LLINK(P) and RLINK(P) according to the rules

$$ \text{If } LLINK(P) = \Lambda \text{ then } LTAG(P) = 1 \text{ and } LLINK(P) \leftarrow $P, \quad \text{If } RLINK(P) = \Lambda \text{ then } RTAG(P) = 1 \text{ and } RLINK(P) \leftarrow P$, $$

and to set LTAG(P) = 0 or RTAG(P) = 0 when the corresponding link is nonempty. The procedure should avoid recomputation of inorder traversal steps by making use of the notation P$, which gives the inorder successor of NODE(P), and $P, which gives the inorder predecessor.

The algorithm proceeds in two conceptual stages: first, the inorder traversal of T using Algorithm T to generate a sequence of nodes; second, the assignment of thread pointers based on the predecessor-successor relations in that sequence.

Let prev be a variable storing the previously visited node in inorder. Initialize prev <- LOC(T) to denote the external pointer to the tree. Then traverse T in inorder according to Algorithm T. At each visit of a node P, execute the following operations:

  1. Left thread assignment. If LLINK(P) = \Lambda, set LTAG(P) <- 1 and LLINK(P) <- prev. Otherwise set LTAG(P) <- 0.
  2. Right thread assignment for previous node. If prev \ne LOC(T) and RLINK(prev) = \Lambda, set RTAG(prev) <- 1 and RLINK(prev) <- P. Otherwise set RTAG(prev) <- 0.
  3. Update prev. Set prev <- P.

Upon completion of the traversal, RLINK(prev) may be null; in that case set RTAG(prev) <- 1 and RLINK(prev) <- LOC(T) to terminate the sequence of threads. All other links already point to existing subtrees and have LTAG or RTAG set to 0.

Formally, the threaded tree algorithm may be stated as follows:

Algorithm TT (Thread an unthreaded binary tree). Input: pointer T to an unthreaded binary tree. Output: threaded binary tree with LTAG, RTAG fields.

TT1. [Initialize.] Set prev <- LOC(T). Initialize stack A <- empty. Set P <- T.

TT2. [Traverse left.] If P \ne \Lambda, push P onto A and set P <- LLINK(P). Repeat TT2. Otherwise proceed to TT3.

TT3. [Visit node.] If A is empty, go to TT6. Otherwise pop P from A.

Set

$$ \text{if } LLINK(P) = \Lambda \text{ then } LTAG(P) <- 1, LLINK(P) <- prev \text{ else } LTAG(P) <- 0. $$

If prev \ne LOC(T) and RLINK(prev) = \Lambda, set RTAG(prev) <- 1, RLINK(prev) <- P; otherwise set RTAG(prev) <- 0.

Set prev <- P.

TT4. [Traverse right.] Set P <- RLINK(P) and return to TT2.

TT5. [Termination.] After all nodes have been visited, if RLINK(prev) = \Lambda, set RTAG(prev) <- 1, RLINK(prev) <- LOC(T).

TT6. [End.] The tree T is now threaded in symmetric (inorder) order. ∎

Correctness argument. The sequence of nodes visited by steps TT2-TT4 is exactly the inorder sequence of T by the argument in Section 2.3.1 and by Algorithm T. At the moment P is visited, prev points to the inorder predecessor of NODE(P) (or LOC(T) if none exists). Assigning LLINK(P) <- prev for null left links ensures that every left thread points to the predecessor. Similarly, updating RLINK(prev) <- P for null right links guarantees that every right thread points to the successor. The stack preserves the traversal history and ensures that each subtree is fully traversed before visiting the root, preserving the inorder property. Upon termination, RLINK(prev) is assigned to LOC(T) to signal the end of the threaded sequence. Each node with a non-null left or right link has LTAG or RTAG set to 0, preserving standard subtree connections.

This algorithm executes exactly one assignment to LLINK(P) and LTAG(P) per node when the left link is null, and exactly one assignment to RLINK(prev) and RTAG(prev) per node when the right link is null. Since the inorder traversal touches each node exactly once, all nodes are correctly threaded. The algorithm uses a single stack of maximum depth equal to the height of the tree, which is consistent with the resource requirements of Algorithm T.

This completes the solution. ∎