```(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))
```