<< Previous exercise (2.62)
| Index |
Next exercise (2.64) >>
a. The trees shown in figure 2-16 can be written as:
(define fig2-16-1 '(7 (3 (1 () ()) (5 () ())) (9 () (11 () ()))))
(define fig2-16-2 '(3 (1 () ()) (7 (5 () ()) (9 () (11 () ())))))
(define fig2-16-3 '(5 (3 (1 () ()) ()) (9 (7 () ()) (11 () ()))))
Using either function, the trees all evaluate to the same list:
(1 3 5 7 9 11)
b. The first function is of O(n log n) complexity. The second function is of O(n) complexity.
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.
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)
T(n) = 2*T(n/2) + O(1)
Solving the above equation, we get T(n) = O(n)