; 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