SICP Exercise 2.63

sicp

Question

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 '()))
  1. 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?
  2. 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?

Answer

As for question one, yes, they do produce the same result. The two functions basically traverse the tree in the same way, starting with the left trees and using cons to build up the result list. The only difference is that in the case of the first function, the result list is not a separate variable, but built up through recursion. The second function is recursive as well, but uses a variable to store the operation results.

(define l1 (list 7
                 (list 3 (list 1 '() '()) (list 5 '() '()))
                 (list 9 '() (list 11 '() '()))))
(define l2 (list 3
                 (list 1 '() '())
                 (list 7 (list 5 '() '()) (list 9 '() (list 11 '() '())))))
(define l3 (list 5
                 (list 3 (list 1 '() '()) '())
                 (list 9 (list 7 '() '())  (list 11 '() '()))))

(tree->list-1 l1)
(tree->list-2 l1)
(tree->list-1 l2)
(tree->list-2 l2)
(tree->list-1 l3)
(tree->list-2 l3)

Results:

(1 3 5 7 9 11)
(1 3 5 7 9 11)
(1 3 5 7 9 11)
(1 3 5 7 9 11)
(1 3 5 7 9 11)
(1 3 5 7 9 11)

However, the order of growth does differ between the two implementations.

The first function uses append, which itself is \(\Theta(n)\). This function is called approximately \(\log n\) times, giving us a total complexity of \(\Theta(n \log n)\).

The second function uses cons rather than append, which is \(\Theta(1)\). Since cons is called once for each entry, the total complexity here should be \(\Theta(n)\).