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).


NOTE: Instead of using empty for leaf nodes we are going to false. This is the way the book does it. Please be aware of this.
NOTE: Your parameters must be in the same order as they are specified here. If you are unsure, ask your TA. You will lose credit otherwise.
NOTE: Follow the HW Skeleton, these homeworks will be autograded and must be in the specified format. You will lose credit otherwise.
NOTE: Remember that you must be in "Intermediate Scheme".

1. Similar to Problem 14.2.3 but with a few differences



1. The 2 structs we will be using are as follows:

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

   Remember to do the analysis for both of these
   
   
2. The data definition for a BST or node is as follows:

   	 A binary-search-tree(BST) is either:
   	     1. false; or
   	     2. (make-node mydata lft rgt) is a BST where
   	        (a) mydata is a data instance,
   	        (b) lft and rgt are BSTs,
   	        (c) all data in lft are smaller than mydata, and
   	        (d) all data in rgt are larger than mydata.
                   (e) data is compared by ssn, so it is the determining factor for comparing
   	 

   Remember to create the data definition and analysis for data
   
   
3. Here is the form your function calls should have:

   	 (inorder <BST>)
                   

4. The most trivial calls would look like this:

   	 (inorder false)
                  or
   	 (inorder (make-node ((make-data 123456789 'name-1) false false)))
   
                   

5. The following is a sample of what should happen if someone tries to run your function in Dr. Scheme.
   
   

   Welcome to DrScheme, version 103p1. Language: Intermediate Student. > (inorder (make-node (make-data 63 'Terry) (make-node (make-data 29 'John) (make-node (make-data 15 'Graham) (make-node (make-data 10 'Connie) false false) (make-node (make-data 24 'Brian) false false)) false) (make-node (make-data 89 'Jones) (make-node (make-data 77 'Eric) false false) (make-node (make-data 95 'Michael) false (make-node (make-data 99 'Mandy) false false))))) (list 10 15 24 29 63 77 89 95 99) > (inorder false) empty

   
   The first example above "(inorder (make-node 63 ..." is the same tree as appears in Figure 38 (left) from the book, thats Tree A. These are special 2 digit SSNs.

6. Assume all soc numbers are unique in your BST.



2. Similar to Problem 14.2.5 but with a few differences



1. The data definition for a BST is the same as the last problem.
   
   
2. Since we have the data struct, you should create this struct with number and name given and then create a BST node with this newly created data instance.
   
   
3. Here is the form your function calls should have:

   	 (create-bst <BST> <number> <symbol>)
                   

4. The most trivial calls would look like this:

   	 (create-bst false 123456789 'name-1)
                  or
   	 (create-bst (make-node ((make-data 123456789 'name-1) false false)) 987654321 'name-2)
   
                   

5. The following is a sample of what should happen if someone tries to run your function in Dr. Scheme.
   
   

   Welcome to DrScheme, version 103p1. Language: Intermediate Student. > (create-bst (make-node (make-data 42 'Ben) false (make-node (make-data 314 'Jerry) false false)) 100 'Scoop) (make-node (make-data 42 'Ben) false (make-node (make-data 314 'Jerry) (make-node (make-data 100 'Scoop) false false) false)) > (create-bst false 3 'Moe) (make-node (make-data 3 'Moe) false false)

   
   Again special 1, 2 and 3 digit SSNs.

6. Assume all soc numbers are unique in your BST. Adding duplicates need not be handled or anticipated in any way.
   
   
7. Think of this function as "adding" to a BST. Remember that a BST is ALWAYS sorted.



3. Similar to Problem 14.2.6 but with a few differences



1. The data definition for a BST is the same as the last problem in addition to the list-of-number/name data analysis from the problem defintion
   
   
2. Do NOT write a function that does the same thing as create-bst. create-bst is a function that adds onto a BST. This function's job is to create a BST from scratch based on the list that is passed in. However, you may use the function create-bst if you see reason to do so.
   
   
3. Here is the form your function calls should have:

   	 (create-bst-from-list <list>)
                   

4. The most trivial calls would look like this:

   	 (create-bst-from-list '())
            ;; notice we are in Intermediate Scheme so we recommend using '() instead of empty
                  or
   	 (create-bst-from-list (list (list 992358595 'bryan)
                                        (list 776546546 'ryan)
                                        (list 246354645 'david)
                                        (list 101957321 'janet)
                                        (list 956249621 'travis)
                                        (list 153269413 'james)
                                        (list 899897413 'matt)
                                        (list 296596331 'arjun)))
                  or
            (define sample-list (list (list 992358595 'bryan)
                                      (list 776546546 'ryan)
                                      (list 246354645 'david)
                                      (list 101957321 'janet)
                                      (list 956249621 'travis)
                                      (list 153269413 'james)
                                      (list 899897413 'matt)
                                      (list 296596331 'arjun)))
            (create-bst-from-list sample-list)
                   

   Note: these are NOT the SSN's of the TAs
   
   

5. The following is a sample of what should happen if someone tries to run your function in Dr. Scheme.
   
   

   Welcome to DrScheme, version 103p1. Language: Intermediate Student. > (create-bst-from-list '()) ;; in Intermediate Scheme we can use '() instead of empty false > (create-bst-from-list (list (list 992358595 'LoneStar) (list 776546546 'DarkHelmet) (list 246354645 'Vespa) (list 101957321 'Scroob) (list 996249621 'Yogert))) (make-node (make-data 992358595 'LoneStar) (make-node (make-data 776546546 'DarkHelmet) (make-node (make-data 246354645 'Vespa) (make-node (make-data 101957321 'Scroob) false false) false) false) (make-node (make-data 996249621 'Yogert) false false))

6. Assume all soc numbers are unique in your BST. Adding duplicates need not be handled or anticipated in any way.