TAOCP 2.3.1 Exercise 19
Exercise 19 asks for an algorithm analogous to Algorithm `S`, but for the calculation of the preorder successor.
Section 2.3.1: Traversing Binary Trees
Exercise 19. [27] Design an algorithm analogous to Algorithm S for the calculation of P‡ in (a) a right-threaded binary tree; (b) a fully threaded binary tree. If possible, the average running time of your algorithm should be at most a small constant, when P is a random node of the tree.
Verified: yes
Solve time: 1m41s
Setup
Exercise 19 asks for an algorithm analogous to Algorithm S, but for the calculation of the preorder successor. Since exercise 17 has already requested an algorithm for P* in a fully threaded tree with a list head, the present exercise concerns the same problem under weaker threading assumptions.
Let HEAD be the list head. In a right-threaded tree, RTAG(P)=1 means that RLINK(P)=P$; there are no left threads. In a fully threaded tree, the conventions of the section apply:
$$ LTAG(P)=1 \iff LLINK(P)=$P, $$
$$ RTAG(P)=1 \iff RLINK(P)=P$. $$
The problem is to compute the preorder successor of NODE(P), denoted by P*, using only the links and tags of the threaded representation.
The preorder definition is
$$ \text{root},\quad \text{left subtree},\quad \text{right subtree}. $$
Hence the successor of a node is determined by the first subtree that remains to be traversed after that node has been visited.
Solution
(a) Right-threaded binary tree
The preorder successor is characterized as follows.
If LLINK(P)\ne\Lambda, the left subtree is traversed immediately after visiting NODE(P), hence
$$ P*=LLINK(P). $$
If LLINK(P)=\Lambda but RTAG(P)=0, the node has no left subtree and a genuine right subtree; therefore
$$ P*=RLINK(P). $$
The remaining case is
$$ LLINK(P)=\Lambda,\qquad RTAG(P)=1. $$
Then P is a leaf. The thread leads to the inorder successor, not to the preorder successor, so further motion may be necessary.
Let Q initially be P. Repeatedly replace Q by RLINK(Q) while RTAG(Q)=1. Every such step climbs through a chain of inorder-successor threads. Let R be the first node reached with RTAG(R)=0, or let R=HEAD if no such node exists.
If R=HEAD, the preorder traversal has ended and
$$ P*=HEAD. $$
Otherwise R possesses a genuine right subtree. All nodes in the left subtree of R have already been traversed, because the thread chain was followed upward from the last node of that left subtree. Therefore the next preorder node is the root of the right subtree of R, namely
$$ P*=RLINK(R). $$
This yields the algorithm.
P1. If LLINK(P)\ne\Lambda, set Q\leftarrow LLINK(P) and terminate.
P2. If RTAG(P)=0, set Q\leftarrow RLINK(P) and terminate.
P3. Set Q\leftarrow P.
P4. While RTAG(Q)=1, set Q\leftarrow RLINK(Q).
P5. If Q=HEAD, terminate. Otherwise set
$$ Q\leftarrow RLINK(Q) $$
and terminate.
The average running time is bounded by a small constant. Every execution of step P4 traverses a thread. During a complete preorder traversal, each thread can be crossed at most once in this manner. Since the number of threads is $O(n)$, the total cost of all executions of P4 over the entire traversal is $O(n)$. Therefore the average cost per successor computation is $O(1)$.
(b) Fully threaded binary tree
The same preorder characterization applies, but left-thread information permits a simpler test.
If LTAG(P)=0, a genuine left child exists. Hence
$$ P*=LLINK(P). $$
Assume now that LTAG(P)=1. Then no left subtree exists.
If RTAG(P)=0, a genuine right child exists, and therefore
$$ P*=RLINK(P). $$
The remaining case is
$$ LTAG(P)=1,\qquad RTAG(P)=1. $$
The node is a leaf. Proceed upward through inorder-successor threads until a node having a genuine right child is found. Let that node be R. If HEAD is reached first, the preorder traversal is complete. Otherwise the next preorder node is the root of the unvisited right subtree of R, namely RLINK(R).
Hence:
F1. If LTAG(P)=0, set Q\leftarrow LLINK(P) and terminate.
F2. If RTAG(P)=0, set Q\leftarrow RLINK(P) and terminate.
F3. Set Q\leftarrow P.
F4. While RTAG(Q)=1, set Q\leftarrow RLINK(Q).
F5. If Q=HEAD, terminate. Otherwise set
$$ Q\leftarrow RLINK(Q) $$
and terminate.
The amortized analysis is identical to that of part (a). Each thread followed in step F4 can contribute at most once during a complete traversal, so the average time per computation of P* is $O(1)$.
Verification
Consider the binary tree whose preorder sequence is given in (3):
$$ A\ B\ D\ C\ E\ G\ F\ H\ J. $$
For the leaf D, the algorithm follows the inorder-thread chain
$$ D \rightarrow B \rightarrow A, $$
where A is the first node having a genuine right subtree. The algorithm then returns
$$ RLINK(A)=C, $$
which is exactly the preorder successor of D.
For the leaf G, the inorder thread leads directly to C. Since C has a genuine right subtree, the algorithm returns
$$ RLINK(C)=F, $$
which agrees with (3).
For the final node J, repeated thread following reaches HEAD; therefore the algorithm returns HEAD, which is the prescribed value when no preorder successor exists.
These cases cover all possibilities:
$$ \text{left child exists},\qquad \text{right child exists but no left child},\qquad \text{leaf}. $$
Therefore the algorithms correctly compute P*.
This completes the proof.
∎
Notes
The fully threaded version differs from the right-threaded version only in the initial test. The upward search through inorder-successor threads is the same in both cases. The reason is structural: when a preorder traversal leaves a leaf, the next node is determined by the nearest ancestor whose right subtree has not yet been traversed. The thread chain provides exactly the information needed to locate that ancestor without a stack.