TAOCP 2.3.1 Exercise 31

Section 2.3.1: Traversing Binary Trees

Exercise 31. [23] Design an algorithm that "erases" a right-threaded binary tree. Your algorithm should return all of the tree nodes except the list head to the AVAIL list, and it should make the list head signify an empty binary tree. Assume that each node has the fields LLINK, RLINK, RTAG; use no auxiliary stack.

Verified: no
Solve time: 56s

Solution

Let T be the pointer to the right-threaded binary tree, and let AVAIL be the head of the list of available nodes. We wish to erase all nodes of the tree except the list head, returning them to AVAIL, without using an auxiliary stack. A right-threaded tree has the property that RTAG(P) = 1 if and only if RLINK(P) points to the inorder successor of P; otherwise RTAG(P) = 0 and RLINK(P) points to a genuine right subtree. The idea is to traverse the tree in inorder, visiting each node exactly once, and returning it to AVAIL after its children (if any) have been processed. Since right threads do not lead to unvisited subtrees, we can traverse without a stack.

Let P be a working pointer and Q a temporary variable used to hold nodes to be returned to AVAIL. The following algorithm accomplishes the task.

Algorithm E (Erase a right-threaded binary tree without a stack).

E1. [Initialize.] Set P <- T. Set T <- Λ to indicate the tree is empty.

E2. [Traverse to leftmost node.] While P ≠ Λ and LLINK(P) ≠ Λ, set P <- LLINK(P).

E3. [Process node.] Set Q <- P. If RTAG(P) = 1, set P <- RLINK(P); else set P <- RLINK(P). (If RLINK(P) is a subtree, P now points to its leftmost node after repeating E2.)

E4. [Return node to AVAIL.] Set RLINK(Q) <- AVAIL; set AVAIL <- Q.

E5. [Continue traversal.] If P ≠ Λ, repeat E2–E5; otherwise terminate. ∎

Correctness argument

Let n be the number of nodes in the tree. We prove by induction on n that all nodes are returned to AVAIL exactly once and that T is empty.

Base case ($n = 0$). Then T = Λ, step E1 sets T <- Λ and P <- Λ. Step E5 terminates immediately. No nodes exist, so the claim holds.

Inductive step. Suppose the claim holds for all trees with fewer than $n$ nodes, $n > 0$. Let P_0 be the initial value of P in step E2. The loop in E2 moves P to the leftmost node of the tree. Let L denote the left subtree of P_0 (possibly empty). By the induction hypothesis, traversal of L via repeated application of E2–E5 returns all nodes of L to AVAIL exactly once. After visiting the leftmost node, step E3 sets P to its inorder successor using either the right-thread link or the actual right subtree. If the right subtree exists, its leftmost node is reached in the next iteration of E2, and by induction all nodes of the right subtree are processed similarly. Each node is returned to AVAIL in step E4 after its left subtree has been erased, ensuring no node is lost or revisited. Since every node has a finite path to the rightmost node, the process terminates with P = Λ and all nodes linked into AVAIL.

Step E1 guarantees that T = Λ at the end, so the tree is erased. Every node has been linked exactly once to AVAIL, preserving the invariant that the list contains exactly the erased nodes.

This completes the proof. ∎

Complexity

Each node is visited once in E2–E5. Each link assignment in E4 counts as one operation. No auxiliary storage is used beyond the temporary variable Q.

The final tree head satisfies $T = Λ$, and AVAIL contains all $n$ nodes of the original tree.

$\boxed{T \text{ is empty and all nodes are returned to } AVAIL}$