sicp-ex-2.63

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 results. because they both are inorder-traversal.
b. assume n is the number of nodes in the tree, T(n) is the total time costed by the procedure.
for tree->list-1:
T(n) = 2*T(n/2) + O(n/2) (considering the procedure "append")
solved above equation, T(n) = O(n*logn)
for tree-list-2:
T(n) = 2*T(n/2) + O(1)
we can get T(n) = O(n)