COS 371: Programming Languages
Spring 2022
hw2: Binary search trees
Due: Friday, 02/11 at 22:00
This is a solo/pair programming assignment. You may either work alone or with one other student of your choice. If you are pair programming, this means that you and your partner should be doing the entirety of this assignment side-by-side, on a single computer, where one person is "driving" and the other is "navigating." (Or a remote equivalent of this experience.) Set a timer to swap every 15 minutes, say. You can choose your favourite from this online timer page. You are not allowed to divide-and-conquer the assignment by each working separately on half of it. If your schedule does not allow you to find enough time to meet together to complete the entire assignment side-by-side, you should opt to do the assignment solo instead.
1. Goals
To write Scheme functions that implement integer binary search trees. To test Scheme code using a unit-testing framework.2. Introduction
We will represent an empty (binary) tree as an empty list.
A nonempty binary tree can be represented as a list of three entries:
- the root node's value (an integer),
- the root node's left subtree, and
- the root node's right subtree.
(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 (BST) 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.
3. Specification
Write the following functions. See hints in the next section before starting.
- Functions to create binary trees and access their elements:
(null-binary-tree)
Return an empty binary tree.(entry node)
(left node)
(right node)
Given a nonempty binary treenode
, return the value, left subtree, and right subtree, respectively. The behaviour whennode
is not a nonempty binary tree is unspecified. In other words, ifnode
is an empty binary tree or ifnode
is not a binary tree at all, your function can do anything it wants.(make-binary-tree element left-subtree right-subtree)
Return a new binary tree whose root node's value is element, left subtree is left-subtree, and right subtree is right-subtree. Error checks are not necessary.
- Functions to check emptiness and validity:
(binary-tree? node)
Return true (#t
) ifnode
represents a valid binary tree, and false (#f
) otherwise.(bst? node)
Return true ifnode
represents a valid binary search tree (BST), and false otherwise.(null-binary-tree? node)
Return true if node represents an empty binary tree, and false otherwise.
- Functions on valid BSTs:
In the following, the behaviour when
bst
is not a valid BST is unspecified. In other words, if the input is not a legal BST, your function can do anything it wants.(member? v bst)
Return#t
ifbst
contains a node with valuev
, and#f
otherwise.- (preorder bst)
- (inorder bst)
- (postorder bst)
Return a list containing all values in bst in the order obtained from a preorder, inorder, or postorder traversal, respectively. Preorder visits the root before traversing the left and then the right subtrees recursively via preorder traversal. Inorder visits the root in between traversing left and right subtrees (recursively via inorder traversal). Postorder visits the root after traversing left and right subtrees (recursively via postorder traversal). (insert v bst)
Return a new binary search tree identical to bst but with integer v appearing in its proper location. (Do not changebst
.) 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 (a copy of) the original tree without changing it.
4. Notes
- Read and follow the Scheme style and grading guidelines linked from the course website.
- As always, you should employ an incremental development strategy. Write a few functions, test them, and then move on to other functions. Think through what order you should develop these functions: some of the functions listed first will benefit from functions listed later!
- One (good) way to test your code is using RackUnit.
First, add
(#%require rackunit)
to the top of your file. (The funny syntax is because this is not valid Scheme code, but a way to communicate with DrRacket.) This special command loads therackunit
module, which makescheck-equal?
available for your use. Try the following to see what happens when a test fails:(check-equal? (+ 3 4) 5)
After defining a function, write a test by checking whether its output is what you want:
(check-equal? (entry '(5 () ())) 5)
If your
entry
is correct, the expression above produces no output. - Leave (correct)
rackunit
tests in your submission. There should be no output when we run your submission, which tells us that all your tests are passing. We can append our own tests to the end of your file to make sure you pass our tests, too. You must use recursion, and not iteration. You may not use side-effects (e.g., set!).
5. Optional Challenges
I will mention some optional challenges from time to time. These will sometimes range from fairly easy to ridiculously hard. You should pursue them only for your own leisure. They are not to be turned in for extra credit.- Try to minimize code duplication in the three traversal functions.
- Implement a BST-backed dictionary (think Java's
TreeMap
). (remove v bst)
Return a new BST withv
removed.- Make the BST self-balancing.
6. Submission
Submit your code in a file called bst.scm.
If you are part of a pair, one of you should submit to Moodle. The other should submit nothing. (If you submit two copies, you will make us waste time grading it twice.) Make sure both of your names appear as authors at the top of the file. You will receive the same grade and comments via Moodle.
Starting from this homework, you will be graded on style.
Start early, have fun, and discuss questions on Moodle.