;A binary search tree is either empty or it has three parts, a root, which is an element, 
;and two subtrees, a left and a right one.  Both of the subtrees are themselves binary 
;search trees.  Furthermore, all of the elements in the left subtree are smaller than 
;or equal to the root, while all of the elements in the right subtree are greater than 
;or equal to the root.
  

(define make-empty-tree
  (lambda () '()))
(define make-nonempty-tree
  (lambda (root left right)
    (list root left right)))

(define root car)
(define left-subtree cadr)
(define right-subtree caddr)

(define empty-tree? null?)

(define tree-1 
  '(4 (1 (0 () ()) (3 (2 () ()) ())) (5 () (6 () (9 () ())))))

(define display-tree
  (lambda (tree)
    (define display-bar
      (lambda (n)
        (cond
          ((= n 0) 12)
          (else (display"-") (display-bar (- n 1))))))
    (define display-with-indent
      (lambda (tree level)
        (cond 
          ((empty-tree? tree) (display-bar level) (newline)
            12)
          (else (display-bar level) 
                (display (root tree))
                (newline)
                (display-with-indent (left-subtree tree)(+ level 3))
                (display-with-indent (right-subtree tree)(+ level 3))))))
    (display-with-indent tree 0)))


(define preorder
  (lambda (tree)
    (if (empty-tree? tree)
        '()
        (cons (root tree)
              (append (preorder (left-subtree tree))
                      (preorder (right-subtree tree)))))))

(define preorder
  (lambda (tree)
    (preorder-onto tree '())))

(define preorder-onto
  (lambda (tree list)
    (if (empty-tree? tree)
        list
        (cons (root tree)
              (preorder-onto (left-subtree tree)
                             (preorder-onto (right-subtree tree)
                                            list))))))