Ex-2.63

;a
Both procedures do in-order traversal of the tree to create the list, hence both produce the same results.

;List produced for figures of 2.16 is same
(define tree-1 '(7 (3 (1 () ()) (5 () ()))
                   (9 () (11 () ()))))
(define tree-2 '(3 (1 () ())
                   (7 (5 () ()) (9 () (11 () ())))))
(define tree-3 '(5 (3 (1 () ()) ())
                   (9 (7 () ()) (11 () ()))))
;which is (1 3 5 7 9 11) 

;b

For tree->list-1
t(n) = steps-to-append + t(n/2) + t(n/2)
     = a + bn + 2t(n/2)
solving above recurrance equation will get
its O(nlogn)

For tree->list-2
t(n) = 2t(n/2)
its O(n)

clearly tree->list-1 is slower version.