CS 251: Programming Languages

Spring 2018

hw2: Binary search trees

Due: Wednesday, 04/04 at 22:00

This is a pair programming assignment. If you are on a team, 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." Set a timer to swap every 15 minutes, say. You can choose your favourite from this online timer page. Make sure your sound volume is audible, but not so loud to disturb the people around you.

1. Goals

To write Scheme functions that implement integer binary search trees. To test Scheme code using a unit-testing framework.

2. Introduction

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.

Nonempty left and right subtrees are themselves lists of three elements, similarly. 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 (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 tree node, return the value, left subtree, and right subtree, respectively. The behaviour when node is not a nonempty binary tree is unspecified. In other words, if node is an empty binary tree or if node 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) if node represents a valid binary tree, and false (#f) otherwise.
- (bst? node)
  Return true if node 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 if bst contains a node with value v, 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 change bst.) 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 the rackunit module, which makes check-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 with v removed.
Make the BST self-balancing.

6. Submission

Submit your code in a file called bst.scm. We will be grading this using Moodle's anonymous grading capabilities, so make sure that your names are not included in your file.

If you are part of a pair, one of you should submit to Moodle. The other should submit nothing. 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.