TAOCP 2.3.1 Exercise 12

We aim to construct an algorithm analogous to Algorithm `T` that traverses a binary tree in _preorder_, visiting each node exactly once, and then prove its correctness by induction on the number of no...

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.1: Traversing Binary Trees

Exercise 12. [22] Design an algorithm analogous to Algorithm T that traverses a binary tree in preorder, and prove that your algorithm is correct.

Verified: no
Solve time: 37s

Solution

We aim to construct an algorithm analogous to Algorithm T that traverses a binary tree in preorder, visiting each node exactly once, and then prove its correctness by induction on the number of nodes. Let T be a pointer to a binary tree represented as in (2), and let A be an auxiliary stack as in Algorithm T.

Algorithm P (Traverse binary tree in preorder).

P1. [Initialize.] Set stack A empty, and set P <- T.

P2. [P = Λ?] If P = Λ, go to step P5.

P3. [Visit P.] Visit NODE(P). Then, if RLINK(P) ≠ Λ, push RLINK(P) onto stack A. Next, set P <- LLINK(P) and return to step P2.

P4. [Pop from stack.] If stack A is empty, terminate the algorithm; otherwise pop the top of A into P and return to step P2.

P5. [Finish.] Terminate. ∎

Correctness Proof

We prove that Algorithm P traverses a binary tree in preorder by induction on $n$, the number of nodes in the tree.

Base case $(n = 0)$. If P = Λ initially, step P2 leads directly to step P5, and no nodes are visited. This coincides with the definition of a preorder traversal of an empty tree.

Inductive step $(n > 0)$. Let P_0 be the initial value of P at step P2. Since P_0 ≠ Λ, step P3 visits NODE(P_0). If RLINK(P_0) ≠ Λ, RLINK(P_0) is pushed onto the stack A, and P <- LLINK(P_0). Let the left subtree of P_0 have $k < n$ nodes. By the induction hypothesis, the recursive execution of steps P2-P5 starting from P = LLINK(P_0) traverses the left subtree in preorder, leaving A with RLINK(P_0) at its top if RLINK(P_0) ≠ Λ.

After finishing the left subtree, step P4 pops the top of A into P, which is precisely RLINK(P_0) if it exists. Now the preorder traversal of the right subtree occurs, again by the induction hypothesis. When the stack is empty, the algorithm terminates at step P5.

At each stage, the algorithm first visits the current root, then traverses the left subtree, and finally traverses the right subtree (by popping from the stack). Therefore, the traversal order exactly matches the recursive definition of preorder.

This proves that every node is visited exactly once, in preorder.

This completes the proof. ∎

Step Count Analysis (Optional Verification)

Let $n$ be the number of nodes in the tree. Denote by $s_i$ the number of times step $P_i$ is executed. Then:

  • Step P1 is executed once.
  • Step P2 is executed $n+1$ times: once for each nonempty node and once when P = Λ at the end.
  • Step P3 is executed $n$ times, once for each node.
  • Step P4 is executed $n$ times minus 1 if the stack is empty initially (depending on tree shape).
  • Step P5 is executed once.

The stack never contains more entries than the length of the longest path of right children, analogous to the analysis in Exercise 10.

Notes

The essential idea is to visit each node before descending to its left subtree and to remember right subtrees using a stack. This mirrors Algorithm T while respecting the preorder rule. The correctness proof closely parallels the inductive argument used for Algorithm T, with the only modification being the order of visiting the root.