sicp exercise 2.63

;; Exercise 2.63.  Each of the following two procedures converts a binary tree to a list.

;; (define (tree->list-1 tree)
;;   (if (null? tree)
;;       NULL
;;       (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 NULL))

;; 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?

;; 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?


;; a.
;;

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

(define (tree->list-1 tree)
  (if (null? tree)
      NULL
      (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 NULL))

(define tree1 (list 7 (list 3 (list 1 NULL NULL) (list 5 NULL NULL)) (list 9 NULL (list 11 NULL NULL))))
(define tree2 (list 3 (list 1 NULL NULL) (list 7 (list 5 NULL NULL) (list 9 NULL (list 11 NULL NULL)))))
(define tree3 (make-tree 5
                         (make-tree 3
                                    (make-tree 1 NULL NULL)
                                    NULL)
                         (make-tree 9
                                    (make-tree 7 NULL NULL)
                                    (make-tree 11 NULL NULL))))

(display tree1) (newline)
(display tree2) (newline)
(display tree3) (newline)

(display (tree->list-1 tree1)) (newline)
(display (tree->list-1 tree2)) (newline)
(display (tree->list-1 tree3)) (newline)
(display (tree->list-2 tree1)) (newline)
(display (tree->list-2 tree2)) (newline)
(display (tree->list-2 tree3)) (newline)


;; b.

;; the procedure tree->list-2 is faster that the tree->list-1