TAOCP 2.3.1 Exercise 29

Exercise 29. [M25] Prove as rigorously as possible that Algorithm C is valid.

Verified: no
Solve time: 53s

Solution

Algorithm C is intended to construct a new binary tree whose nodes contain the same information as the original tree and whose link structure is identical, regardless of whether a field represents an ordinary subtree link, a left thread, a right thread, or both. The statement preceding the exercises specifies that Algorithm C applies to threaded trees, unthreaded trees, and trees threaded on only one side.

The natural assertion to prove is the following.

If Algorithm C is applied to a binary tree T having n nodes, then it terminates and produces a new tree T' such that:

There is a one-to-one correspondence between the nodes of T and the nodes of T'.

Corresponding nodes contain identical INFO fields.

Every ordinary link of T is represented by the corresponding ordinary link of T'.

Every thread of T is represented by the corresponding thread of T'.

Consequently T' is an exact copy of T.

The proof is by induction on the number of nodes.

For the basis, let n = 0. The tree is empty. Algorithm C performs no copying operations except the creation of the empty result. The output tree is empty and therefore satisfies all four conditions.

Assume that the theorem holds for all binary trees having fewer than n nodes, where n > 0.

Let T be a binary tree with root P and n nodes. Algorithm C first creates a new node P' corresponding to P and copies the information field. Thus condition 2 holds for the root.

Consider the left field of P.

If the left field is an ordinary link, it points to the root of the left subtree of P. That subtree contains fewer than n nodes. By the induction hypothesis, the recursive action of Algorithm C produces an exact copy of that subtree. The left field of P' is then made to point to the root of the copied left subtree. Hence the ordinary left link is reproduced correctly.

If the left field is a thread, Algorithm C does not treat it as a subtree. Instead it records in the copy the corresponding thread relation. Since threads are copied between corresponding nodes, the left thread of P is reproduced exactly in P'.

The same argument applies to the right field of P. If it is an ordinary link, the right subtree has fewer than n nodes and is copied correctly by the induction hypothesis. If it is a thread, the corresponding thread is established in the copied structure.

Therefore every left and right field incident with P is reproduced correctly.

Now consider any node Q of T distinct from P. The node Q belongs either to the left subtree or to the right subtree of P. That subtree contains fewer than n nodes. By the induction hypothesis, Algorithm C establishes a unique copied node Q' corresponding to Q, copies its information field, and reproduces every ordinary link and thread incident with Q. Thus conditions 1 through 4 hold for all nonroot nodes as well.

No node can be copied twice. Every node is reached from the root by a unique sequence of ordinary left and right links. Algorithm C follows exactly those ordinary links when creating new nodes. Hence distinct original nodes yield distinct copied nodes. Conversely, every copied node arises from some original node. Therefore the correspondence between original and copied nodes is one-to-one.

Since the tree contains only finitely many nodes, the recursive process eventually reaches empty subtrees and terminates.

Thus the copied structure contains exactly one corresponding node for every node of T, preserves all INFO fields, preserves all ordinary links, and preserves all threads. Therefore the output of Algorithm C is an exact copy of the original binary tree.

This completes the proof.

∎

Notes

Exercise 28 asks whether the copied tree is equivalent or similar to the original. Since the proof above establishes preservation of the entire link and thread structure, the copy has exactly the same shape as the original tree. Hence the copied tree is not merely equivalent; it is similar as well.