Binary Search Trees (pair 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, who I will refer to as Person A, 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 (i.e. Person B): after the above is complete, 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.

Person A should continue these steps below. You do not need to wait for Person B to finish the last step above before proceeding forward. (In other words, Person A can set up this whole thing if you like, and Person B can catch up later.)

Person A: Once you see your repository in GitHub (not Repl.it), you should see a button labeled "Work in Repl.it." Click it. That should set up a new repl in Repl.it, and you should be all set to work. Hopefully this is more streamlined than it was in the first assignment, since more of it should be set up, but ask for help if need be. As always, make sure the repl created in Repl.it is private.

Once you have created the repl, click the "Share" button at the top right in Repl.it, and invite your partner, i.e. Person B. (If you're working alone, skip this step.) 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.

… and you should be all set to work!

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

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

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

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

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

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