1 (define (entry tree) (car tree))
2 (define (left-branch tree) (cadr tree))
3 (define (right-branch tree) (caddr tree))
4 (define (make-tree entry left right)
5 (list entry left right))
7 (define (element-of-set? x set)
11 (element-of-set? x (left-branch set)))
13 (element-of-set? x (right-branch set)))))
15 (define (adjoin-set x set)
16 (cond ((null? set) (make-tree x '() '()))
17 ((= x (entry set)) set)
19 (make-tree (entry set)
20 (adjoin-set x (left-branch set))
23 (make-tree (entry set)
25 (adjoin-set x (right-branch set))))))
26 (define (tree->list-1 tree)
29 (append (tree->list-1 (left-branch tree))
31 (tree->list-1 (right-branch tree))))))
32 (define (tree->list-2 tree)
33 (define (copy-to-list tree result-list)
36 (copy-to-list (left-branch tree)
38 (copy-to-list (right-branch tree)
40 (copy-to-list tree '()))
42 ;; 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?
44 ;; Yes, they produce the same result for every tree. They both produce '(1, 3, 5, 7, 9, 11)
46 ;; 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?
48 ;; No, the second procedure is faster. Each procedure makes around n calls to itself (slightly more calls since there are 2 extra per tree with empty leaves). However, the first procedure uses append whereas the second one uses cons. Append has order of growth of (length list1), so I'm guessing the overall order of growth for tree->list-1 is n^2? whereas it is n? for tree->list-2.
