Homework 3: Binary Search Trees

This is a "pair" assignment, which means that you and your partner should use the pair programming model. You should be physically together, sharing a computer and both looking at the same screen.

Each partner has an active role to play during pair programming - please review the instructions on Moodle about pair programming, and make sure you understand what you should be doing when you are the navigator and when you are the driver. You should make sure that over the course of an assignment that you each spend roughly the same amount of time "driving." My recommendation is to set a timer and switch drivers every 10-15 minute.

If pair programming in real-time doesn't work for you and your partner, then you will need to amicably split up and work individually. If you choose this option, you must communicate that to me [Anna]. Please do so as soon as that decision is made. If you split, a new partner typically cannot be assigned until the rest of the class switches partners.

Download the folder with the starter code from the link below. Like for previous homeworks, unzip the folder and move it to where you'd like: most likely the folder for the Docker container. Then get started in VS Code.

If when running tests you run into a permissions error, you can fix this by running the following code in the terminal:

chmod a+x test-e test-m

This tells the computer that all users should be permitted to execute (run) the files test-e and test-m.

Click here to download the starter files

(value bst)
(left bst)
(right bst)

These functions return the value of the current node, the left subtree, and the right subtree, respectively, of bst. If bst is empty or if bst does not contain three entries where the last two are lists, return #f.

(make-bst elt left-bst right-bst)

This function returns a new tree whose root node is elt, left subtree is left-bst, and right subtree is right-bst. You should check that elt is in fact a number, and that left-bst and right-bst are either empty lists or lists of three elements each where the last two are lists. Return #f if the input is bad. (You do not need to recursively check all the way down to see if the tree is completely well-formed, though the last capstone function at the end of the assignment will ask you to do this.)

(preorder bst)

Return a list containing all values in bst in the order obtained from a preorder traversal (visit the root of bst, then do a preorder traversal of the left subtree, then do a preeorder traversal of the right subtree).

(inorder bst)

Return a list containing all values in bst in the order obtained from an inorder traversal (do an inorder traversal of the left subtree, then visit the root of bst, then do an inorder traversal of the right subtree).

(postorder bst)

Return a list containing all values in bst in the order obtained from a postorder traversal (do a postorder traversal of the left subtree, then do a postorder traversal of the right subtree, then visit the root of bst).

(insert v bst)

Return a new binary search tree identical to bst but with integer v appearing in its proper location. The tree pointed to by bst should not change. Smaller values are inserted to the left of a node, larger values to the right of a node. If v is already in the tree, just return the original tree without changing it. You may assume that bst and all its subtrees are valid binary search trees.

(bst-from-list lst)

Returns a binary search tree obtained by inserting the integers in lst one-by-one, from the left of the list, into an initially empty binary search tree.

** proper-tree

(proper-tree? bst)

Returns #t if the tree is well-formed, and #f otherwise. Presumably, any tree you create via the above code should be well-formed if you have written your code correctly.

As with previous assignments, there are M tests and E tests. See the section of Scheme Intro 2 labeled "How to test your work" if you need a refresher on how to run these tests.