<< Previous exercise (2.62) | Index | Next exercise (2.64) >>

a. Both procedures produce the same result because they both are in-order traversals.

b. Let T(n) be the time taken by the procedure for a balanced tree with n nodes.

For tree->list-1:

**T(n) = 2*T(n/2) + O(n/2)** (as the procedure *append* takes linear time)

Solving above equation, we get **T(n) = O(n * log n)**

For tree->list-2:

**T(n) = 2*T(n/2) + O(1)**

Solving the above equation, we get **T(n) = O(n)**

a. The trees shown in figure 2-16 can be written as:

Using either function, the trees all evaluate to the same list:

b. The first function is of O(n log n) complexity. The second function is of O(n) complexity.