Homework 3: Binary Search Trees

You'll download the folder with the starter code from the link below. Like for homeworks 1 and 2, unzip the folder and move it to where you'd like: the folder for the Docker container if you're using Docker, or COURSES if you're not. Then get started in VS Code (see Homework 1 if you get stuck).

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.

(entry bst)
(left bst)
(right bst)

These functions return the node, left subtree, and 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 final 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? bst)

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

Go back and look at the sections at the end of Scheme Intro 2 labeled "How to test your work". Everything there about how to run M tests and E tests applies identically here.

You'll submit your work on Gradescope. First, create a CollaborationsAndSources.txt file in the same folder as your code. In that file, indicate in what ways (if any) you collaborated with other people on this assignment and . Indicate any people you talked about the assignment with besides me (Anna) and our prefect. Did you share strategies with anyone else? Talk about any annoying errors and get advice? These are fine things to do, and you should note them in the CollaborationsAndSources.txt file. Give the names of people you talked with and some description of your interactions. If you used any resources outside of our course materials, that is also something to note in Collaborations.txt. If you didn't talk with anyone or use any outside sources, please note that explicitly in CollaborationsAndSources.txt. Look back at the Scheme Intro 1 instructions if you want more details on the CollaborationsAndSources.txt file.

After making CollaborationsAndSources.txt and finishing the assignment, upload your files on Gradescope. Note that if you submit a zip, you should submit a zip of the files, not a zip of the folder that contains the files. If all tests fail on Gradescope but they're working on your machine, this is likely the problem.

On Gradescope, you should see autograder output for the same tests as you ran locally. There is a very small but possible chance that you have coded something highly unexpected that causes the tests to pass on the computer you’re working on, but not on Gradescope. We will be grading this assignment based on the results of the tests on Gradescope, so you should make sure to pay attention to how the tests run there as well when you submit.

For grading, you'll earn at least an M if the following conditions are all met:

• All M tests pass
• A visual inspection of your code shows that you have not hyper-tailored your code to pass the tests. Hyper-tailoring your code would be doing things like checking for the exact input from the test, meaning you haven't written your code in a way that would work for similar inputs.
• You have a CollaborationsAndSources.txt with the information described above.
• The work is turned in by the late deadline.

You'll earn an E if:

• All conditions above for an M are met.
• All the E tests pass.
• Your code is not significantly more complex than needed to accomplish the task.
• You have a comment before each function describing what the function does (its input/output behavior, not a play-by-play of "first checks… then makes a recursive call …").
• The homework is turned in by the regular deadline, or it is turned in by the late deadline and you elect to use a late token (by stating this in a regrade reguest after grading is complete).

If your code does not meet the criteria for an M or an E, then you'll earn a grade of NA (Not Assessable) or SP (Some Progress) for the assignment. Not Assessable means that your submission does not have an attempt at one or more functions in the assignment or was not turned in by the late deadline. Some Progress means that your submission has some code (in the correct language) for all functions in the assignment, but that the code does not pass all of the M tests, is hyper-tailored to the tests, and/or is missing a CollaborationsAndSources.txt file.

Good luck, ask questions, and have fun!