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))
6 
7 (define (element-of-set? x set)
8   (cond ((null? set) #f)
9 	((= x (entry set)) #t)
10 	((< x (entry set))
11 	 (element-of-set? x (left-branch set)))
12 	((> x (entry set))
13 	 (element-of-set? x (right-branch set)))))
14 
15 (define (adjoin-set x set)
16   (cond ((null? set) (make-tree x '() '()))
17 	((= x (entry set)) set)
18 	((< x (entry set))
19 	 (make-tree (entry set)
20 		    (adjoin-set x (left-branch set))
21 		    (right-branch set)))
22 	((> x (entry set))
23 	 (make-tree (entry set)
24 		    (left-branch set)
25 		    (adjoin-set x (right-branch set))))))
26 (define (tree->list-1 tree)
27   (if (null? tree)
28       '()
29       (append (tree->list-1 (left-branch tree))
30 	      (cons (entry tree)
31 		    (tree->list-1 (right-branch tree))))))
32 (define (tree->list-2 tree)
33   (define (copy-to-list tree result-list)
34     (if (null? tree)
35 	result-list
36 	(copy-to-list (left-branch tree)
37 		      (cons (entry tree)
38 			    (copy-to-list (right-branch tree)
39 					  result-list)))))
40   (copy-to-list tree '()))
41 
42 (define (list->tree elements)
43   (car (partial-tree elements (length elements))))
44 
45 (define (partial-tree elts n)
46   (if (= n 0)
47       (cons '() elts)
48       (let ((left-size (quotient (- n 1) 2)))
49 	(let ((left-result (partial-tree elts left-size)))
50 	  (let ((left-tree (car left-result))
51 		(non-left-elts (cdr left-result))
52 		(right-size (- n (+ left-size 1))))
53 	    (let ((this-entry (car non-left-elts))
54 		  (right-result (partial-tree (cdr non-left-elts)
55 					      right-size)))
56 	      (let ((right-tree (car right-result))
57 		    (remaining-elts (cdr right-result)))
58 		(cons (make-tree this-entry left-tree right-tree)
59 		      remaining-elts))))))))
60 
61 ;; a. Write a short paragraph explaining as clearly as you can how partial-tree works. Draw the tree produced by list->tree for the list (1 3 5 7 9 11).
62 
63 ;; If we want a tree with 0 elements in it, we just return an empty tree (nil). Otherwise, we're going to build a tree by finding the middle element of a list rounded down (so if we had 6 elements, the middle element will be 3. If we have 7 elements, it will be 4). We then create a tree with the middle element as the entry of the tree and then call ourselves recursively to build the left-branch of the tree and the right-branch of the tree. We then return this tree along with any elements that have not been put into the tree. The reason we need the remaining elements is because it helps us quickly pass along all the elements of the list that go into the entry and right branch of the tree.
64 
65 ;; b. What is the order of growth in the number of steps required by list->tree to convert a list of n elements? 
66 
67 ;; We call partial-tree O(n) times for a list of n elements (a bit more again because we also call it when n = 0). It looks like the order of growth is roughly O(n).