TAOCP 2.3.2 Exercise 14

Section 2.3.2: Binary Tree Representation of Trees

Exercise 14. [M21] How long does it take the program of exercise 13 to copy a tree with n nodes?

Verified: yes
Solve time: 1m15s

Solution

Exercise 14 asks for the running time of the COPY subroutine of Exercise 13. The hint for Exercise 13 directs us to adapt Algorithm 2.3.1C to right-threaded binary trees. Therefore the copied tree is traversed in the same manner as a threaded binary tree traversal, with the additional work of creating corresponding nodes in the new tree.

Let the original tree contain $n$ nodes. During the copy process, each original node is encountered exactly once, because the traversal visits every node of the threaded binary tree exactly once. For each node visited, the routine performs a bounded amount of work:

1. Allocate one new node.
2. Copy the fields TYPE and INFO.
3. Establish the corresponding left link.
4. Establish the corresponding right link or right thread.
5. Perform the constant amount of bookkeeping needed to continue the traversal.

The traversal mechanism inherited from Algorithm 2.3.1C has the fundamental property that each link of the threaded binary tree is followed at most once. A binary tree with $n$ nodes has exactly $n-1$ genuine left or right child links, and the right-threaded representation contains one right pointer per node. Hence the total number of pointer traversals is proportional to $n$.

More precisely, the routine performs one node-construction operation for each of the $n$ nodes and a constant amount of additional work associated with each pointer traversal. Since the number of nodes and traversed pointers are both linear in $n$, there exist constants $c_1,c_2>0$ such that

$$ c_1 n \le T(n) \le c_2 n . $$

Therefore

$$ T(n)=\Theta(n). $$

The copy routine requires time proportional to the number of nodes in the tree.

$$ \boxed{\Theta(n)} $$