Exercise 2.63.  Each of the following two procedures converts a binary 
tree to a list.

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))

a. Do the two procedures produce the same result for every tree? If not, 
how do the results differ? What lists do the two procedures produce for 
the trees in figure 2.16?

————————————————————————————————————————————————————————————————————————

Yes.  Both procedures produce the list of elements in the tree in 
ascending order.

Both procedures return '() if the tree is empty.  Thus for the trivial 
case, both produce the correct result.  For any other case, there are 
simple inductive proofs for both.

tree->list-1 produces the ordered (by inductive hypothesis) list of the 
elements of the left branch followed by the entry followed by the 
ordered list of the right branch.  Since the greatest element in the 
left branch is guaranteed to be less than the entry, and the lowest 
element in the right branch is guaranteed to be greater, the result will 
be correctly ordered.

tree->list-2 is a little more awkward to prove.  The internal procedure 
copy-to-list (on a non-empty tree) produces the result of copy-to-list 
on the left branch, providing a result-list which consists of the entry, 
followed by the ordered (by hypothesis) list of elements in the right 
branch, followed by the previous result-list.  Assuming the previous 
result list is ordered and dominates the right branch, then this list 
will be ordered.  If this list is ordered, then the call to copy-on-list 
on the left branch will have an ordered result-list, the lowest element 
of which will be greater than any element of the left branch, so our 
assumption is valid.


b. Do the two procedures have the same order of growth in the number of 
steps required to convert a balanced tree with n elements to a list? If 
not, which one grows more slowly?

————————————————————————————————————————————————————————————————————————

The second procedure grows more slowly.

It requires consing each element of the tree onto a list, while the 
first procedure additionally requires a number of append operations.