To better understand binary search trees by implementing some of their methods yourself. You will also get more practice with recursive methods and thinking.
You should complete this on Wednesday Oct 20th, 2021, but it isn’t due until Friday Oct 22nd, 2021 at 5pm.
You should work on this with your in-class partner, but you both need to submit separately.
If you finish it outside of class without your partner, note which sections you completed together and which you completed separately in your
Mount the COURSES drive and remember to save everything into STUWORK. If you don’t do this, everything you write will disappear when you log out!!!!
- Create a new folder in your STUWORK called
- Create your
Collaborations.txtdocument in that folder
- Download the starter code and put it into your BSTLab folder
- Open your BSTLab folder in VSCode
I’ve provided you with a class
BSTNode that holds four things:
Stringwhich is the key for the node and what will be used for ordering the nodes
intwhich is the value for the node, and you can imagine is something that you are trying to store, such as the number of times the key has appeared in a document
BSTNodeleft, which is the left child of this node
BSTNoderight, which is the right child of this node
I’ve also provided you with the start of the
BST class, which includes a couple of useful methods already:
printTree()prints the tree fairly nicely. It only works if the keys are single character strings, so I recommend sticking with capital letters, but it should help you visualize the tree. There is a lot of helper code for this method that appears at the end of the class that you shouldn’t worry about.
test()manually adds some nodes to the tree so that you can see what it looks like before you’ve implemented
addis the public method for adding to the tree. It checks if the root node is null and then just calls the recursive helper function
Your task: In
main you should first create a
BST, call the
test method on it, and then call the
printTree() method to see how things work. Make sure that you understand why the tree prints out the way that it does.
You will next implement the
There are four cases that you need to handle in
getHelper: the base case and the cases for if the keys are equal, one is less than the other, and vice versa.
Think about what the two base cases should be for this recursive method. What is the simplest situation when looking for a node in the tree? Implement those first. Remember that since you’re dealing with
Strings, you should use
.equalsto check for equality.
Now decide on what the two recursive cases are. What are the situations where you aren’t done and you need to make another call to
getHelperthat moves you closer to the base cases? You should use the
compareTomethod because the keys are
Strings. However, it isn’t limited to returning only -1, 0, or 1. With strings, it can return any positive or negative value, so you need to just check if it returns a value less than or greater than 0.
getmethod by retrieving the values associated with the keys that are set in the
You will now implement the
The construction of this recursive method is a bit more complicated than
get because you need to attach the node to the tree in the right place.
One of your base cases is if the keys are equal, because this version of a binary search tree just doesn’t add the new node and returns false. Implement that functionality first.
If the keys aren’t equal, you need to figure out if you are going to insert the new node to the left or to the right of the
subRoot. This could lead to either a base case (if there is room) or a recursive case (if there is already a child there).
Once you know which side of the subtree you are going to be adding the new node, you also need to check if there is already a child node there or not. If there isn’t a child on that side, you have a base case and you should set the child as
If there is already a child on that side, you should make a recursive call to
addHelperwith the appropriate parameters. Also be sure to think about what you should return in both these cases.
If you haven’t already, implement the code for adding the node to the other side of the tree as well.
Test your code by adding several more nodes to the tree
Think about why you couldn’t have a base case that just checks if
subRootis null and sets
subRootequal to the new node. We’ll discuss as a class.
If you have extra time, try
addHelperso that instead of returning a
boolean, they return a
BSTNodeand have a structure more similar to
getHelper. Be careful with making sure that a duplicate key doesn’t erase the previous key.
Compress your files as a zip, and upload that zip to Moodle under the appropriate assignment. Remember that partners need to submit their code separately and you should share the code you wrote in class with your partner.
This activity is not a homework assignment. That means that you’re evaluated on whether you attempted all parts of it, but your work will not be graded for correctness as long as a clear effort has been made. If you aren’t able to complete some parts, great ways to indicate clear effort are to reach out for help before the deadline (note ways you did so in your Collaborations.txt file) and to use comments in the code to indicate things you tried but what went wrong/where you got stuck.