TAOCP 2.3.1 Exercise 33

Section 2.3.1: Traversing Binary Trees

Exercise 33. [30] There is more than one way to thread a tree! Consider the following representation, using three fields LTAG, LLINK, RLINK in each node:

LTAG(P): defined the same as in a threaded binary tree;
LLINK(P): always equal to P*;
RLINK(P): defined the same as in an unthreaded binary tree.

Discuss insertion algorithms for such a representation, and write out the copying algorithm, Algorithm C, in detail for this representation.

Verified: no
Solve time: 37s

Setup

Let $T$ be a binary tree represented in memory with nodes containing three fields: LTAG(P), LLINK(P), RLINK(P). The definitions are as follows:

LTAG(P) is set as in a standard threaded binary tree: LTAG(P) = 1 if LLINK(P) is a thread, 0 otherwise.
LLINK(P) always stores the preorder successor of P: LLINK(P) = P*.
RLINK(P) behaves as in an unthreaded binary tree: it points to the right subtree of P if nonempty, or is \Lambda if the right subtree is empty.

We are asked to discuss insertion algorithms for this representation and to formulate a copying algorithm, Algorithm C, that duplicates the tree in this representation.

The main goals are:

Show how to insert a node into a tree where LLINK(P) = P* and RLINK is unthreaded, updating all necessary fields.
Construct a general copying procedure that preserves the invariant LLINK(P) = P* and the correct values of RLINK and LTAG.

Let NODE(P) denote the contents of P, LLINK(P) the preorder successor of P, RLINK(P) the right child, and LTAG(P) the tag bit indicating whether LLINK(P) is a thread.

Solution

Insertion Algorithm

Let X be the new node to insert, and T be a pointer to the root of the tree. We assume a binary search tree structure for ordering, so the placement of X is determined by comparing keys. Let P traverse the tree to find the appropriate insertion point.

Step I1. [Initialize.] Set P <- T and Q <- \Lambda.

Step I2. [Search position.] While P \ne \Lambda, do:

Set Q <- P.
If KEY(X) < KEY(P), move left: P <- LLINK(P) if LTAG(P) = 0 (ordinary left child), else P <- \Lambda.
If KEY(X) \ge KEY(P), move right: P <- RLINK(P).

After this loop, Q points to the parent under which X will be inserted.

Step I3. [Attach X.]

If KEY(X) < KEY(Q):
Set RLINK(X) <- \Lambda.
Set LLINK(X) <- Q*.
Set LTAG(X) <- 1.
Set LLINK(Q) <- X and LTAG(Q) <- 0.
If KEY(X) \ge KEY(Q):
Set RLINK(Q) <- X.
Set LLINK(X) <- X* (to be computed according to preorder traversal).
Set LTAG(X) appropriately (0 if LLINK(X) points to a genuine left child, 1 if it points to a preorder successor).

Step I4. [Update preorder links.]

The key invariant is that for any node P, LLINK(P) = P*. Therefore, after insertion, we must update LLINK fields for all affected nodes. Let S be the predecessor of X in preorder; set LLINK(S) <- X if S previously pointed to the old successor. Set LLINK(X) <- X* as computed from the traversal of the updated tree.

This insertion ensures that RLINK correctly points to the right subtree, and LLINK preserves the preorder successor invariant. LTAG indicates whether LLINK is a thread (points to a nonchild) or a left child.

Copying Algorithm C

We now construct Algorithm C to copy a tree in this representation. Let T be the original tree, and T' the target tree. The procedure recursively duplicates nodes while maintaining the preorder links.

Algorithm C [Copy tree with preorder threads].

C1. [Base case.] If P = \Lambda, return \Lambda.

C2. [Create node.] Allocate a new node Q. Set NODE(Q) <- NODE(P).

C3. [Copy left child.]

If LTAG(P) = 0, then the left subtree exists:

Set LLINK(Q) <- C(LLINK(P)).
Set LTAG(Q) <- 0.

Otherwise, the left link is a thread:

Set LLINK(Q) <- Q* (preorder successor of Q in the new tree).
Set LTAG(Q) <- 1.

C4. [Copy right subtree.]

If RLINK(P) \ne \Lambda, then:

Set RLINK(Q) <- C(RLINK(P)).

Else, set RLINK(Q) <- \Lambda.

C5. [Return.] Return Q.

This algorithm recursively constructs the tree. After recursion, the LLINK of each node points to its preorder successor, and LTAG is set correctly. Preorder links may require a postprocessing pass to finalize LLINK(Q) = Q* because preorder successors of the rightmost nodes are not immediately available during the first traversal.

Verification

The invariant LLINK(P) = P* is maintained as follows:

For nodes with a genuine left child, recursion copies the subtree, preserving the preorder order. LLINK(Q) initially points to the copy of the left child, which is also Q* if the left subtree exists.
For nodes whose left link is a thread, LLINK(Q) is set to Q* in step C3, matching the preorder successor in the new tree.
Right subtrees are copied recursively, preserving the unthreaded structure.
LTAG(Q) correctly reflects whether LLINK(Q) points to a genuine child or a thread.
Each recursive call returns the root of a copied subtree, ensuring that RLINK points to the correct node in the copy.

By induction on the number of nodes, the copied tree satisfies the same preorder-threaded invariant as the original. Preorder links for rightmost nodes may be finalized by a simple traversal of the copied tree using LLINK to set any remaining LTAG = 1 links correctly.

Insertion algorithm correctness is verified by noting that it preserves the BST order and updates LLINK and LTAG consistently. The preorder successor invariant is restored after the necessary adjustments in step I4.

This completes the proof.

∎

Notes

An alternative is to maintain a global pointer to the last inserted node in preorder, updating its LLINK to the new node X during insertion. This avoids a postprocessing pass for LLINK.
The copying algorithm could also be implemented iteratively using a stack, similar to Algorithm T, but recursion provides a clearer mapping from the original tree to its copy.
For general trees (not binary search trees), KEY comparisons can be replaced by a parent–child linkage scheme without affecting the preorder-thread invariants.