In the first parts of this lab, we will be creating our own implementation of the binary search tree (BST) data structure to better understand its implementation and behavior.
Similar to Lab 6, Java does not provide an interface or abstract class that represents a BST. Thus, we will build the BST data structure entirely from scratch following the descriptions we used in lecture. We will again be using generics for the implementation so that the tree can store any type of data as elements.
ReadMe
Even though Java does not provide a binary search tree implementation, it does use balanced versions of BSTs behind the scene in some of its most popular implementations of other data structures, such as TreeSet and TreeMap.
In Visual Studio Code, create a new file in your GitHub repository called MyBinarySearchTreeNode.java. Within this file, you should create a new class using the code:
public class MyBinarySearchTreeNode<T extends Comparable>
which restricts the type of data T stored in the tree to be something that implements the Comparable interface so that we know that we can use its compareTo method for sorting data in the BST.
ReadMe
As you are implementing your solutions, do not forget to include documentation using Javadocs! This is important practice to get into the habit of, and it will be a portion of your solution grade for the remainder of the semester.
The class itself (at the top), each instance variable, and each method should have a short Javadoc comment.
Hint
Some of the ideas for this class are similar to the MyTreeNode<T> class that you implemented in Lab 6, so please feel free to refer back to your previous solution whenever it is helpful!
Refining our code for new use cases is a classic type of task we perform as computer scientists.
Your MyBinarySearchTreeNode class should have four private instance variables:
item: the item of type T that is stored by the nodeparent: the parent MyBinarySearchTreeNode<T> of this node (which will be null for the root node)leftChild: the MyBinarySearchTreeNode<T> that is the left child this tree node (which might be null)rightChild: the MyBinarySearchTreeNode<T> that is the right child this tree node (which might be null)All four of the instance variables should be private so that their access (especially assigning values) can be controlled through the MyBinarySearchTreeNode class.
The MyBinarySearchTreeNode class should have two constructors:
The first private constructor is for non-root nodes – it should take as parameters an item to store in the node and a parent MyBinaryTreeSearchNode to save as the parent of the new node. The leftChild and rightChild should be null to start (they will be added later as needed).
The second public constructor is for the root node – it should take as a single parameter the item to store in the node. This constructor should call the other constructor, instead of duplicating its work.
Hint
Recall that we had one constructor call another in Lab 3, if you need a refresher of how that process works.
ReadMe
Only the second constructor is public because outside of this class, a developer can only make new root nodes for trees. Non-root children should only be created through the insert method that we will develop in Part 2 of the lab, which will call the first private constructor.
Since we made our instance variables private, we can add “getter” methods in order to still be able to retrieve values from outside of the class. You should add two such methods:
public T getItem(), which returns the value of the item instance variablepublic MyBinarySearchTreeNode<T> getParent(), which returns the value of the parent instance variableReadMe
We do not need getter methods for the children because we will retrieve nodes from the tree using the find method implemented in Part 4 of the lab.
Before moving on to the next part of the lab, we should create unit tests to verify our implementation so far and help us find and remove any bugs. As in previous labs, we can create a Java file that will contain our unit tests by right clicking anywhere in the MyBinarySearchTreeNode.java file and selecting “Source Action” from the right click menu. Then, select “Generate Tests”. Use the default name proposed by the IDE of MyBinarySearchTreeNodeTest. Next, it will prompt you with what methods you want to create tests for. Select the getItem method for now.
Inside the newly created MyBinarySearchTreeNodeTest.java file, create unit tests verifying that the getItem and getParent methods work properly. We will create more tests in the next part of the lab.
Don’t forget to frequently save your progress to GitHub using the add/commit/push commands with git.