; The below abstraction for binary trees is implemented with
; a function in order to force you to use selectors to inspect
; tree data in the interpreter.
(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 tet 'toasterhead)  ; tet = the empty tree
(define (empty-tree? tree) 
  (eq? tree tet))
(define (leaf? bintree)
  (and (not (empty-tree? bintree))
       (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.

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

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)

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

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.

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

5. Write the function map-tree which takes a function and a binary search tree as its inputs and returns a binary search tree with the same structure and the data in the tree modified by the function.

> (datum (map-tree square bst))
225
> (datum (left (map-tree (lambda (x) (+ x 1))  bst)))
7

6. Write the code for a tree that looks like this:

                   31
                  /  \
                 /    \
               18     44
                \
                 \
                 25

7. Is it possible that the tree in Problem 6 is a binary search tree? How can you tell?