Exercise 2.64.  The following procedure list->tree converts an ordered 
list to a balanced binary tree. The helper procedure partial-tree takes 
as arguments an integer n and list of at least n elements and constructs 
a balanced tree containing the first n elements of the list. The result 
returned by partial-tree is a pair (formed with cons) whose car is the 
constructed tree and whose cdr is the list of elements not included in 
the tree.

(define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

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).

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

Partial-tree returns a tree having n elements.

If n = 0, it simply returns the empty tree.

Otherwise, it:
- calculates the size of the left branch, as half the value of n, 
  rounded down if n is odd.
- constructs the left branch and the remainder of the input list by 
  calling partial-tree.
- finds the size of the right branch, by subtracting the size of the 
  left branch, plus one for this node's entry, from n.
- pulls the car of the non-left-elts out to be the entry.  Since n is at 
  least 1, and the size of the left branch was rounded down, the number 
  of elements not in the left branch will be at least 1, so this 
  application of car will not fail.
- constructs the right branch and the remainder of the input list by 
  calling partial-tree.
- returns the remainder of the input list, and the tree with the entry 
  and left and right sub-trees that were calculated.

        7
       / \
      3   9
     / \   \
    1   5  11

(both wrong, is discussed on IRC)


b. What is the order of growth in the number of steps required by 
list->tree to convert a list of n elements?

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

Linear.