Starting MyBinarySearchTreeNode

Data Structure Overview

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 scenes in some of its most popular implementations of other data structures, such as TreeSet and TreeMap.

Getting Started

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.

Instance Variables

Your MyBinarySearchTreeNode class should have four private instance variables:

  1. item: the item of type T that is stored by the node
  2. parent: the parent MyBinarySearchTreeNode<T> of this node (which will be null for the root node)
  3. leftChild: the MyBinarySearchTreeNode<T> that is the left child this tree node (which might be null)
  4. 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.

Constructors

The MyBinarySearchTreeNode class should have two constructors:

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

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

Getter Methods

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:

  1. public T getItem(), which returns the value of the item instance variable
  2. public MyBinarySearchTreeNode<T> getParent(), which returns the value of the parent instance variable
README

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.

Testing Our Progress

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.

Committing Your Progress

Donā€™t forget to frequently save your progress to GitHub using the add/commit/push commands with git.