Binary Search Trees (Part 1)

0. Complete the Prerequisites

Before continuing on, make sure you’re caught up on the lectures through 6/27. Also make sure to pull the starter code.

1. First 5 BST methods

In this assignment your task is to complete a series of algorithms involving Binary Search Trees. The method signatures and their explanations that you need to implement are provided in the BST.java Interface. We have provided the implementation for an EmptyBST, and it is your job to provide the outstanding implementation for a non-empty BST in the NonEmptyBST class. The methods left for you to complete have a “TODO” comment above them. We have provided getHeight, getRight, getLeft, getElement, and isEmpty.

You can test your implemention in the Main class. For this assignment, we didn’t provide a toString method for you like we did with LinkedLists, so printing out the bst will give you something like ex08.NonEmptyBST@5674cd4d. To get more useful information, you might consider writing a helper toString method to give yourself a nice string representation of a BST, or making use of the different traversal methods to get information about what your tree looks like. This is optional.

The entire BST programming task has been broken up into two smaller exercises, with the methods required by the BST interface being divided up between ex08 and ex09.

For ex08, we are expecting you to complete, size, findMin, findMax, insert, and printInOrderTraversal. The rest will count as part of ex09, but feel free to work ahead.

2. Make a Backup Checkpoint “Commit”

“Push” your work up to GitHub for backup. By creating “commits”, which you can think of as versioned checkpoints in your workspace, you are not at risk of losing your work. It’s easy to revert back to an old version or to restore your entire workspace on a different computer.

1. Select the Git menu along the top of your screen and then choose “Commit”.
2. Notice the files listed under Changes. These are files you’ve made modifications to since your last backup.
3. Ensure all the files that you’d like to backup are selected. Your cursor should be inside of a message box where you will write a nice description of the modifications you’ve made to your code, like “Finished EX04!”, and then hit the “Commit” button.
   • If you do not want to backup all changed files, you can select them individually. For this course you’re encouraged to back everything up.
   • IntelliJ might tell you there are some warnings or errors here, and you should just commit anyway!
4. If you open the Git at the bottom of your screen, you should see this commit added to your chain of git commits. However, it has just been added to your local main branch, and needs to be pushed to your remote backup.
5. Select the Git menu along the top of your screen again and then choose “Push”.
6. A pop-up should appear that displays: “main -> backup : main”, which means your latest local commit on the local main branch is going to be pushed to the main branch on the remote backup. If you see “main -> origin : main”, just click where it says origin and select backup. Hit the “Push” button.
7. If you want to see your backed up work on Github, navigate to the following URL but replace USERNAME with your GitHub username:
   • https://github.com/summer-210/summer210-workspace-USERNAME
   • You can also verify it was pushed successfully by opening the Git view along the bottom of your screen and verifying the latest commit appears on the local and remote branches. (The text next to the tag icons should say backup & main, next to the latest commit message)

4. Submit to Gradescope for Grading

All that’s left now is to hand-in your work on Gradescope for grading.

Before doing so, you need to know that before an assignment’s deadline you can resubmit work as many times as you need to without penalty. Portions of assignments are autograded and will provide near-immediate feedback. We want you to resubmit as many times as it takes you in order to earn full autograding credit!

Login to Gradescope and select the assignment named “EX08 - BSTs Part 1” You’ll see an area to upload a zip file. To produce a zip file for autograding, return back to IntelliJ.

Mac Users

Along the bottom of your window, you should see an option to open a terminal integrated into IntelliJ.

Type the following command (all on a single line):

./submit.sh ex08

In the file explorer pane, look to find the zip file named “ex08_submission.zip”. The script will call it an ex08 submission since that is the package we zipped. If you right click on this file “Open in -> Finder” on Mac, the zip file’s location on your computer will open. Upload this file to Gradescope to submit your work for this exercise.

Windows Users

We are working on rewriting the script to work for Windows! Until then, please navigate to your course workspace in a File Explorer window. Then right click on the src folder in your exercises directory and compress the directory into a zip folder. You can name it “ex08_submission.zip”

When you upload it to Gradescope, please delete any files that showed up in the src/ folder that were not actually part of ex08.