TAOCP 2.3.1 Exercise 17

We are asked to give an algorithm analogous to Algorithm `S` that determines the preorder successor `P*` of a node `P` in a threaded binary tree with a list head as in `(8), (9), (10)`.

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.1: Traversing Binary Trees

Exercise 17. [22] Give an algorithm analogous to Algorithm S for determining P* in a threaded binary tree. Assume that the tree has a list head as in (8), (9), and (10).

Verified: no
Solve time: 36s

Solution

We are asked to give an algorithm analogous to Algorithm S that determines the preorder successor P* of a node P in a threaded binary tree with a list head as in (8), (9), (10). By definition, P* is the address of the node visited immediately after NODE(P) in a preorder traversal. Recall that preorder traversal visits the root first, then the left subtree, then the right subtree. In a threaded binary tree, threads replace null LLINK or RLINK links with pointers to the predecessor or successor in inorder, but the preorder structure is still encoded in the left and right links.

Let P point to a node of the threaded binary tree. Consider the following cases for finding P*.

  1. If LLINK(P) points to a nonempty left subtree (i.e., LTAG(P) = 0), then in preorder traversal, the left child is visited immediately after NODE(P). Therefore, in this case, P* = LLINK(P).
  2. If LLINK(P) is a thread (LTAG(P) = 1), or if there is no left subtree, the next node in preorder is the first node reachable by following RLINK links or threads until a node with a nonempty right subtree is found. Specifically, let Q <- P. While RTAG(Q) = 1 (i.e., RLINK(Q) is a thread), set Q <- RLINK(Q). If RTAG(Q) = 0 (i.e., RLINK(Q) is a genuine right child), then P* = RLINK(Q). If no such right child exists before reaching the list head, the traversal ends and P* = LOC(T).

This reasoning yields the following algorithm.

Algorithm P (Preorder successor in a threaded binary tree). If P points to a node of a threaded binary tree, this algorithm sets Q <- P*.

P1. [Left subtree?] If LTAG(P) = 0, set Q <- LLINK(P) and terminate the algorithm.

P2. [Search right.] Set Q <- P. While RTAG(Q) = 1, set Q <- RLINK(Q). If RTAG(Q) = 0, set Q <- RLINK(Q) and terminate the algorithm. Otherwise, if the list head is reached, set Q <- LOC(T) and terminate. ∎

Justification. Let P be a node with left child LLINK(P) nonempty. Then preorder visits NODE(P) first, followed by the left subtree, so P* = LLINK(P). If LLINK(P) is empty (LTAG(P) = 1), preorder visits the right child of P if it exists. If RLINK(P) is also a thread, then no immediate right child exists, and we must ascend the tree along threads (RLINK links with RTAG = 1) until a node with a genuine right child is found; the preorder successor is the leftmost node of the first right subtree encountered in this process. This corresponds precisely to the above algorithm. The list head serves as a sentinel to indicate the end of traversal.

This algorithm is analogous to Algorithm S and requires only the existing thread fields; no auxiliary stack is needed, and it runs in time proportional to the number of threads traversed.

This completes the solution. ∎