Binary Search Trees (pair assignment)

Table of Contents

1 Pair programming structure

This is a "pair" assignment, which means that if you are working on a team with someone else, you and your partner should do your best to engage in the pair programming model. If at all possible, my recommendation is to use Repl.it, which will allow you to code together remotely using "multiplayer" mode. At any point in time, one of you is "driving," i.e. actually using the keyboard and mouse. The other is actively engaged following along, preventing bugs, and providing ideas. You can communicate with each other via Google Hangouts, Zoom, a phone call, or any other voice approach. In a pinch, you can also use the Repl.it chat window, though having voice communication with each other would be better.

You should make sure that over the course of an assignment that you spend roughly the same amount of time each "driving." I will also ask you to turn in a form rating the work that your partner does. My recommendation is to take turns approximately every 15 minutes or so. Set a timer to help you remember.

If pair programming in real-time just doesn't work for you and your partner, you have options:

  • You can choose to amicably split up and just work individually; or…
  • You can split up the work as evenly as you can, and carefully describe to each other over email or some other form of async communication what you've done and make sure all agree. In that eventuality, you should make sure you understand deeply the code from the other person, or perhaps rewrite it for yourself. You should both suggest and make improvements on each other's code (presumably over email or some other form of async communication).

2 Get started

2.1 Use GitHub classroom to create a repository for your assignment

The first thing you'll need to do is to create a repository for your project using GitHub classroom. If you are working on a team, this repository will be shared, so only one of you should do this. To help reduce a round of communication, I'm going to designate that if you are working in a pair, the member of your team whose Carleton official email address comes first alphabetically should do this next step of setting up the GitHub repository. If you are working alone, then you should do this step.

If you are the designated person above, visit this GitHub classroom link (which I've placed in Moodle). Log into GitHub if your browser prompts you to after you get to GitHub. You should be taken to a screen that invites you to either "Join an existing team" or to "Create a new team". You should create a new team. Please name the team with both of your GitHub usernames. For example, if users FSchiller and StevieP are working together, please name the team FSchiller-StevieP. The order doesn't matter. This will make it easier for the graders to know who the repositories belong to. GitHub should then hopefully respond with a screen that says "You are ready to go!" and supplies you with a link for the repository that you are creating. Click on that link, and you should be taken to the repository. If you've gotten this far, you have successfully created the repository, and you the user who is logged in have access to it. Contact your partner if you have one and tell them that this step worked. (If you are working alone on the project, you can skip the next step.)

The other one of you, after the above is complete, should visit the same GitHub classroom link in the first sentence in the previous paragraph. You'll see the screen asking you to "Join an existing team" or to "Create a new team." You should be able to see the team that your partner created above; click the "Join" button. This should then take you to the "You are ready to go!" screen, and you can hopefully find a link to the repository. Click on it. You now both have access to the same GitHub repository.

2.2 Create a repl in Repl.it (only if you're in a pair)

If you are working individually, you can continue to work in the my-work repl that you created for the last lab, and so you can ignore this step.

If you are working in a pair, the same person who created the repo above should create a new Bash repl called paired-work, making sure that it is private. Once you have created the repl, click the "invite" button at the top, and invite your partner. You can do this by typing in their Carleton email address, or by emailing them directly the sharing link. Sometimes the email is a little slow to send, but it works. Perhaps try both strategies.

2.3 Clone your repository into Repl.it

For the person on your team whose email comes first alphabetically (or just you, if you're working alone), you should now clone the repository from GitHub into Repl.it. If you're in a pair, you can in principle both be watching in multiplayer mode while you do this.

In Repl.it, make sure that you are in your home directory in the terminal window. You can always navigate there by typing

cd ~

in the terminal window. To further confirm, type pwd (which is short for "print working directory.") You should see /home/runner. If you see something different, you're not in the home directory, so try again or ask for help.

In a different browser tab (leave the one with Repl.it open), visit our our class GitHub organization page online. Once you've landed there, you should see the GitHub repository you created in the GitHub Classroom step above. It should be named scheme-bst-username (where username is either own username, or a combination of the two of you if you're working in a pair). Contact us for help if the repository isn't there. Click on that repository title. This should take you to the home page for that repository. There is a green box on the page that says "Clone or download." Click that box, and make sure it says "Clone with HTTPS." Highlight the https link shown, and copy it to the clipboard. The link that you're copying should look something like

https://github.com/carleton251-term/scheme-bst-username.git

… though your username and term will be different.

Then navigate back to the Repl.it tab with the repl that you created above, and click on the terminal window within your new repl. Your next step is to clone the repository from GitHub. To do that, type git clone, then a space, then paste in the URL from the github page that you copied from above. (To paste, you might need to right-click in the terminal window and choose paste rather than using a keyboard shortcut.)

For example, I would type the following, though your username and term will be different:

git clone https://github.com/carleton251-term/scheme-bst-username.git

You'll be prompted to enter your GitHub username and password.

If all goes well, you should receive a directory, titled scheme-bst-username. If you type ls at the prompt, you should be able to see it. It will also appear in your file browser window with Repl.it on the left. Then navigate into that directory by typing in:

cd scheme-bst-username

… and you should be all set to work.

3 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:

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

3.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 is 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 last capstong function at the end of the assignment will ask you to do this.

3.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).

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

4 Capstone work

Work in this section is 100% optional, and not worth any points. Nonetheless, if you're looking for an extra challenge, these are fun additional exercises to try.

4.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.2 proper-tree

(proper-tree? bst)

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

5 Other info

You must use recursion, and not iteration. You may not use side-effects (e.g. set!).

6 How to test and submit your work

Go back and look at the sections at the end of Scheme Lab 2 labeled "How to test your work" and "How to submit your work." Those should apply identically here. Follow those instructions, and you should hopefully be all set.