Note: Webwork will stop accepting this homework at that time - Turn it in well BEFORE then.

No late homework is accepted.

TURN IN THIS ASSIGNMENT USING WEBWORK!!!

Do this homework using DrScheme. Save the file as a ".scm" file--that is, with a .scm extension. If you turn in a non-scm file, you will lose credit.

At the top of your file, include the student info portion of the HW Skeleton (Name, GT Number, HW, Course, Instructor, Lecture Time).

1. Problem 14.2.4.
1. The data definition for a node is as follows:

   	 (define-struct node (ssn name left right))
   	 

2. The data definition for a BST is as follows:

   	 A binary-search-tree(BST) is either:
   	    1. empty; or
   	    2. (make-node soc pn lft rgt) is a BST where
   	       (a) soc is a number,
   	       (b) pn is a symbol,
   	       (c) lft and rgt are BSTs,
   	       (d) all ssn numbers in lft are smaller than soc, and
   	       (e) all ssn numbers in rgt are larger than soc.
   	 

3. Here is the form your function calls should have:

   	 (search-bst <number> <BST>)
   	 

4. The most trivial call would look like this:

   	 (search-bst 123456789 empty)
   	 

5. Assume all soc numbers are unique in your BST.
6. (You do not have to answer the question "Compare searching in binary search trees with searching in sorted lists." for this homework. Think about it though and know the answer.)