Homework 3: Binary Search Trees
Table of Contents
1 Assignment setup
This assignment is to be done individually. You can talk to other people in the class, me, and any of the course staff (graders, lab assistants, prefects) for ideas and to gain assistance. You can get direct help debugging your code from me and any of the course staff, and you're welcome to show us your code during debugging or other conversations. The code that you write should be your own, and you shouldn’t directly show or share your code with other students (although you may discuss general debugging strategies with others). See the course syllabus for more details or just ask me if I can clarify.
1.1 Get started
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
.
2 Your task
Write Scheme functions that implement integer binary search trees. A non-empty binary search tree can be represented as a list of three entries. The first entry is a node's value (an integer), the middle is the node's left subtree, and the last is a node's right subtree. Non-empty left and right subtrees are themselves lists of three elements. An empty tree is represented as an empty list. For example, the list
(5 () ())
represents a tree whose only node is the leaf 5. The list
(5 (3 () (4 () ()) ) ())
represents the tree whose root node is 5 and has only one child, a left child, 3: this left child has only one child, a right child, 4. In a binary search tree it is always the case that values in the left subtree are less than the root's value, and values in the right subtree are greater than the root's value. You may assume that a binary search tree that is given to you will never have duplicate entries, but you will need to make sure when inserting a new entry that it is not a duplicate.
Write the following functions:
2.1 entry, left, right
(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
.
2.2 make-bst
(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.)
As noted in the beginning of the assignment, we're specifically
building integer binary search trees. That means elt
should be an integer
number. You can check for an integer using integer?
. Dybvig gives
the complete documentation for this function. You can check if
something is a list using list?
.
2.3 preorder, inorder, postorder traversals
(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
).
2.4 insert
(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.
3 Optional extensions
Work in this section is 100% optional, and not worth any points. Nonetheless, if you're looking for an extra challenge or ideas on what to practice to study the material, there will be occasional optional extensions sections of homeworks that contain one or more additional exercises to try.
3.1 bst-from-list
(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.
4 Other info
You must use recursion, and not iteration. You may not use
side-effects (e.g. set!
).
5 How to test and submit your work
5.1 Testing your work
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.
5.2 Submitting your work
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 cause the tests 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 see Homework policies for more on this).
- You have a
CollaborationsAndSources.txt
with the information described above.
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 …").
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. 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. You have two revisions to use at any point during the term if
you earn an SP or M grade and would like to revise your code and
have us change your grade.
Good luck, ask questions, and have fun!
Assignment originally designed by Dave Musicant (with input from Stephen Fruend and John Mitchell) - thanks for sharing!