(define (insert item t)
  (cond ((null? t) (list item '() '()))
        ((<= item (car t)) 
         (cons (car t) 
               (list (insert item (cadr t)) (caddr t))))
        (else (cons (car t) 
                    (list (cadr t) (insert item (caddr t)))))))
(define t1 '())
(define t2 (insert 44 t1))
(define t3 (insert 22 t2))
(define t4 (insert 33 t3))
(define t (insert 11 t4))
(define t (insert 9 t))
(define t (insert 16 t))
(define t (insert 55 t))

(define (inorder t)
  (if (not (null? t)) (append (inorder (cadr t)) 
                                       (cons (car t) 
                                       (inorder (caddr t))))
      '() ))

(define (inorder2 t)
  (if (null? t) '()
      (append (inorder (cadr t)) 
              (cons (car t) (inorder (caddr t))))))



Welcome to DrScheme, version 204.
Language: Textual (MzScheme, includes R5RS).

> (inorder t)
(9 11 16 22 33 44 55)

> (define t (insert 88 t))
> (define t (insert 18 t))
> (define t (insert 12 t))
> (inorder2 t)

(9 11 12 16 18 22 33 44 55 88)

> t
(44 (22 (11 (9 () ()) (16 (12 () ()) (18 () ()))) (33 () ())) 
    (55 () (88 () ())))

****************************************************************************
* Part c.  Binary Trees and Scheme                                         *
****************************************************************************

  i.  Write the preorder traversal for the binary trees.
      The output of the preorder traversal will be a list.

 ii.  Write a procedure to find the average of the set of values
      in the binary search tree.  Assume the tree contains only
      numeric atoms.

iii.  Write the procedure to find the maximum depth of the binary
      tree.  Define the depth of an empty tree as depth 0, the 
      depth of a tree with one node as depth 1.