TAOCP 2.3.1 Exercise 21

Let `T` be a pointer to a binary tree of $n$ nodes with the conventional representation `(2)`, that is, each node `P` has two link fields `LLINK(P)` and `RLINK(P)` pointing either to the left or right...

taocpmathematicsalgorithmsvolume-1hard

Section 2.3.1: Traversing Binary Trees

Exercise 21. [33] Design an algorithm that traverses an unthreaded binary tree in inorder without using any auxiliary stack. It is permissible to alter the LLINK and RLINK fields of the tree nodes in any manner whatsoever during the traversal, subject only to the condition that the binary tree should have the conventional representation illustrated in (2) both before and after your algorithm has traversed the tree. No other bits in the tree nodes are available for temporary storage.

Verified: no
Solve time: 32s

Setup

Let T be a pointer to a binary tree of $n$ nodes with the conventional representation (2), that is, each node P has two link fields LLINK(P) and RLINK(P) pointing either to the left or right subtree, or to Λ if the subtree is empty. We are required to traverse this tree in inorder, visiting each node exactly once, without using any auxiliary stack or additional bits in the nodes. Temporary modification of LLINK and RLINK is permitted, provided that after the traversal the tree is restored to its original form.

Let NODE(P) denote the information stored at node P. Let P$ denote the inorder successor of NODE(P). Our goal is to construct a procedure that starts at T and visits all nodes in inorder sequence, ensuring that at each step NODE(P) is visited exactly once, and that the original LLINK and RLINK values are restored when the algorithm terminates.

Solution

We employ the threading during traversal method, also known as the Morris traversal, which creates temporary links to predecessors during the traversal to avoid using a stack. Let current denote the pointer to the node currently being processed. The algorithm proceeds as follows:

Step 1. Initialize current <- T.

Step 2. Repeat while current ≠ Λ:

S2a. If LLINK(current) = Λ, then visit NODE(current) and set current <- RLINK(current).

S2b. Otherwise, locate the inorder predecessor of current in the left subtree:

  • Set pre <- LLINK(current).
  • While RLINK(pre) ≠ Λ and RLINK(pre) ≠ current, set pre <- RLINK(pre).

S2c. If RLINK(pre) = Λ, then create a temporary thread:

  • Set RLINK(pre) <- current.
  • Set current <- LLINK(current).

S2d. Otherwise (RLINK(pre) = current), the left subtree has been traversed:

  • Set RLINK(pre) <- Λ to restore the original tree.
  • Visit NODE(current).
  • Set current <- RLINK(current).

The procedure terminates when current = Λ. At this point, all nodes have been visited in inorder, and the original LLINK and RLINK fields have been restored.

Algorithm (Morris Inorder Traversal)

1. current <- T
2. while current ≠ Λ do
3.     if LLINK(current) = Λ then
4.         visit NODE(current)
5.         current <- RLINK(current)
6.     else
7.         pre <- LLINK(current)
8.         while RLINK(pre) ≠ Λ and RLINK(pre) ≠ current do
9.             pre <- RLINK(pre)
10.        if RLINK(pre) = Λ then
11.            RLINK(pre) <- current
12.            current <- LLINK(current)
13.        else
14.            RLINK(pre) <- Λ
15.            visit NODE(current)
16.            current <- RLINK(current)

Verification

  1. Correctness of visit order. For any node P with LLINK(P) = Λ, the algorithm visits NODE(P) immediately, which is consistent with inorder traversal because there is no left subtree. For LLINK(P) ≠ Λ, the algorithm first finds the inorder predecessor pre of P, temporarily linking pre to P. The left subtree rooted at LLINK(P) is fully traversed before visiting P, ensuring the inorder sequence.
  2. Restoration of tree. Each temporary link RLINK(pre) <- current is later removed when RLINK(pre) = current in step S2d, restoring the original RLINK(pre) = Λ. No LLINK values are permanently altered. Therefore, after traversal, all LLINK and RLINK fields are identical to their original values.
  3. No auxiliary stack. The algorithm uses only pointers current and pre and modifies tree links temporarily. No stack, recursion, or additional bits are required.
  4. Termination. At each step, either current moves to LLINK(current) or RLINK(current), which are either Λ or eventually lead to the right subtree or successor. Since the tree has a finite number of nodes, the traversal terminates after visiting all nodes.

This completes the proof.

∎

Notes

  1. The Morris traversal uses $O(1)$ additional memory and performs at most $2n$ link changes: each non-null LLINK is modified once to create a temporary thread and restored once, while each node is visited exactly once.
  2. A similar approach can be adapted for preorder traversal by visiting NODE(current) immediately after creating a thread, rather than waiting until the left subtree is traversed.
  3. Postorder traversal without a stack is more involved; it generally requires either double threading or temporary modification of both LLINK and RLINK in a more sophisticated manner.