; 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) (define (empty-tree? tree) (eq? tree 'toasterhead)) (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