sicp exercise 2.64

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

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

;; a.
;; The height of a balanced tree of size N is of the order of log(N). The procedure stats by making tree and goes down the left path of the tree for about log(N) times and reaches a point where 'n' becomes 0, that is the point where procedure starts to return back. It places the first element of the list as the entry element of the left most node of the tree. It adjusts the list by removing the first element and starts making the right subtree in the same way. The 'n' for the right subtree is the remaining half of the 'n' for this node. The procedure similarily adjusts the element list for the right subtree and the procedure returns to one level higher.

;; b.
;; The order of growth is O(n)


(define NULL (list))

(define (make-tree item left right) (list item left right))
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))

(define (tree-height tree)
  (cond ((null? tree) 0)
        (else (+ 1 (max (tree-height (left-branch tree))
                        (tree-height (right-branch 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))))))))


(display (list 1 3 5 7 9 11)) (newline)
(display (list->tree (list 1 3 5 7 9 11))) (newline)
(display (tree-height (list->tree (list 1 3 5 7 9 11)))) (newline)


(define (enumerate-list start end next)
  (cond ((> start end) (list))
        (else (cons start
                    (enumerate-list (next start) end next)))))

(define my-list (enumerate-list 1 500 (lambda(x) (+ x 2))))
(display my-list) (newline)
(define  tree-my-list (list->tree my-list))
(display tree-my-list) (newline)
(display (tree-height tree-my-list)) (newline)