Assignment 3 - Binary Search Trees

Due: Monday, April 6, 2026, at 10pm

Starter code: a3_bst.zip
Upload solutions via Gradescope

Goals

This assignment is designed to help you with the following:

  • more practice with Scheme
  • even more practice with lists in Scheme
  • even more practice writing recursive functions

Collaboration policy

For this assignment, you may work alone or with a partner, but you must type up all of the code yourself. (It is therefore unexpected for two code submissions to be completely identical.)

You may also discuss the assignment at a high level with other students.

You should list any student with whom you discussed the assignment, and the manner of discussion (high level, partner, etc.) in your readme.txt file.

If you work alone, you should say so instead.

Assessment

Core requirements:

  • all CR tests pass
  • your code is not hyper-tailored to pass the tests
  • you use recursion, not iteration
  • you do not use side effects (e.g., set!)
  • readme.txt contains your collaboration statement, sources, and reflection

Advanced requirements:

  • satisfy the Core requirements
  • all AD tests pass
  • your code is not significantly more complex than needed to accomplish the task
  • each function has a comment before it describing its high-level behavior
  • your code uses good Scheme coding style

Getting started

As before, you should download the starter files, unzip that file, and copy the folder to where you’ll work (probably your ProgrammingLanguages folder). Refer to the Assignment 1 instructions if you’re unsure what to do.

Part A: Your assignment

In main.scm, you will write Scheme functions that implement integer binary search trees. A non-empty BST 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, where as the list

(5 (3 () (4 () ()) ) ())

represents the three whose root node is 5 and has only one child, a left child. That left node has a value of 3 and is a subtree with only a right child (a node with value 4).

Specifics:

  • 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.

Your task is to write the following functions, described in the next parts:

  • value, left, and right
  • make-bst
  • preorder, inorder, and postorder for traversals
  • insert

Part B: BST basics

The first functions you’ll write are used as follows:

(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, these functions return #f.

Then, you’ll write the following function to create a BST:

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

This function returns a new tree whose root node has value elt and whose left and right subtrees are left-bst and right-bst, respectively. 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, with the last two being lists. In any case, 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 one of the optional extensions will ask you to do this.)

Note: we’re specifically building integer BSTs. 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 similarly check if something is a list using list?.

Part C: Working with a BST

Next, you should write functions to perform traversals in various orders:

(preorder bst)
(inorder bst)
(postorder bst)

  • (preorder bst) - returns a list containing all values in bst in the order obtained from a preorder traversal:

    1. root of bst
    2. preorder traversal of left subtree
    3. preorder traversal of right subtree

  • (inorder bst) - returns a list containing all values in bst in the order obtained from an inorder traversal:

    1. inorder traversal of left subtree
    2. root of bst
    3. inorder traversal of right subtree

  • (postorder bst) - returns a list containing all values in bst in the order obtained from a postorder traversal:

    1. postorder traversal of left subtree
    2. postorder traversal of right subtree
    3. root of bst

Finally, you will write the following procedure to add a new number to our BST:

(insert v bst)

This procedure should return a new BST identical to bst but with integer v appearing in its proper location. The tree pointed to by bst should not change.

If v is already in the tree, just return the original tree without changing it. You may assume that bst and all of its subtrees are valid BSTs.

Part D: Optional extensions

The work in this section is 100% optional and does not contribute to your grade in any way. Still, 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 assignments that contain one or more additional exercises to try.

For this assignment, you are encouraged to implement the following two functions:

(bst-from-list lst)
(proper-tree? bst)

  • (bst-from-list lst) - returns a BST obtained by inserting the integers in lst one-by-one, from the left of the list, into an intially empty BST

  • (proper-tree? bst) - returns #t if the tree is well-formed and #f otherwise (presumably any tree you create using functions in this assignment should be well-formed if your code is correct)

Testing your work

As with the previous assignment, there are CR and AD tests for core and advanced functionality (mapping to requirements above). Look at the instructions from the previous assignment if you want a refresher on how to run this tests.

Submitting your work

As with the previous assignments, you will submit your work in two files.

Scheme code

The file main.scm should contain all of your procedures to implement a BST. Make sure to add a comment above each of your procedures to describe its behavior at a high level (e.g., what it takes as input and what it returns as output).

Readme

For each assignment for this course you will also need to submit a file readme.txt in which you should write:

  1. Your collaborations with anyone on the assignment
  2. Your use of any outside sources on the assignment
  3. Your reflection

You should be specific about your collaborations and sources – they shouldn’t just be empty or lists of names of people. If you worked alone and/or did not use any outside sources, you should say so.

For your reflection, spend a couple of sentences answering the following:

  • Were there any particular issues or challenges you dealt with in completing this assignment?
  • How long did you spend on this assignment?

Submitting to Gradescope

Once you have your two files, you will combine them into a single file using this command:

./zipitup

(make sure you’re in the terminal in the assignment folder). If you get an error about file permissions, first run chmod a+x zipitup.

Submit your .zip file to Gradescope at this link.

Note that it is possible (although unlikely) that the tests will pass on your computer but fail on Gradescope. If this happens, it’s probably because you coded something in an unusual way. Double-check that you’re submitted to the correct assignment and then check if any error messages can help you troubleshoot. If you’re still having issues, check with Tanya.