(define (make-bintree datum left right)
  (lambda (msg)
    (cond ((= msg 0) datum)
          ((= msg 1) left)
          ((= msg 2) right))))

(define (datum bintree) (bintree 0))
(define (left bintree) (bintree 1))
(define (right bintree) (bintree 2))

(define the-empty-tree 'catfish)
(define tet the-empty-tree)  ; shorthand name for the empty tree
(define (empty-tree? tree) (eq? tree 'catfish))
(define (leaf? bintree)
  (and (empty-tree? (left bintree))
       (empty-tree? (right bintree))))

(define bst
  (make-bintree 15
     (make-bintree 6
        (make-bintree 2 tet tet)
        tet)
     (make-bintree 22
        (make-bintree 17
           (make-bintree 16 tet tet)
           (make-bintree 19 tet tet))
        (make-bintree 24 tet tet))))

0. Draw a picture of bst.

                       bst --> 15
                              /  \
                             /    \
                            6      22
                           /      /  \
                          /      /    \
                         2      17    24
                               /  \
                              /    \
                             16    19

1. Write the function contains? which takes a binary search tree of numbers and a datum as its input and returns #t if the datum is in the tree, #f otherwise.

> (contains? bst 17)
#t
> (contains? bst 18)
#f

; FUNCTION: contains
; DOMAIN: Binary search tree of numbers
; RANGE: Boolean
(define (contains? bst num)
  (cond ((empty-tree? bst) #f)
        ((< num (datum bst)) (contains? (left bst) num))
        ((> num (datum bst)) (contains? (right bst) num))
        (else #t)))

2. Write the function inorder which takes a binary search tree as its input and returns a list of the data in ascending order.

> (inorder bst)
(2 6 15 16 17 19 22 24)

; FUNCTION: inorder
; DOMAIN: Binary search tree
; RANGE: List
(define (inorder bst) 
  (cond ((empty-tree? bst) '())
        (else (append (inorder (left bst))
                      (list (datum bst))
                      (inorder (right bst))))))

3. Write the function count-nodes which takes a binary tree (does not have to be a binary search tree) as its input and returns the number of nodes in the tree.

> (count-nodes bst)
8

; FUNCTION: count-nodes 
; DOMAIN: Binary tree (search doesn't matter here)
; RANGE: Integer
(define (count-nodes bt) 
  (cond ((empty-tree? bt) 0)
        (else (+ 1
                 (count-nodes (left bt))
                 (count-nodes (right bt))))))

4. Write the function square-tree which takes a binary tree that contains numbers as its input and returns a binary tree with the same structure and the numbers squared.

; If this were Java, we would explicitly force ourselves to
; make a binary tree of numbers to be returned.  To wit:
; public BST<Integer> squareTree(BST<Integer> bst)
;
; This ain't Java.  So we need to be very careful to return
; the right type of data even though it is not enforced by
; the language.
;
; FUNCTION: square-tree
; DOMAIN: Binary tree of real numbers
; RANGE: Binary tree of real numbers

> (datum (square-tree bst))
225
> (datum (left (square-tree bst)))
36
> (datum (left (left (right (square-tree bst)))))
256

; boring version
(define (square x) (* x x))
(define (square-tree t)
  (cond ((empty-tree? t) tet)
        (else (make-bintree (square (datum t))
                            (square-tree (left t))
                            (square-tree (right t))))))

; entertaining version
(define (map-tree f t)
  (cond ((empty-tree? t) t)
        (else (make-bintree
               (f (datum t))
               (map-tree f (left t))
               (map-tree f (right t))))))
(define (square-tree t)
  (map-tree (lambda (x) (* x x)) t))