Inserting Items

The first operation we want to be able to perform with a BST is to insert a new item into the BST so that we can create a sorted collection of data. We will implement this in a method:

public MyBinarySearchTreeNode<T> insert(T item)

that takes as a parameter the item of type T to add to the tree and returns the newly created MyBinarySearchTreeNode that now stores item. Recall from lecture and our reading that the insert method works recursively:

  1. First compare the current node’s this.item with the argument item. If they are the same, do not insert item (so that we do not have duplicates in our tree) but simply return null signifying that no new node was inserted.
  2. If item is less than this.item, then item needs to be stored somewhere to the left of the current node. If the current node does not have a left child, create and return a new left child storing item. Otherwise, recursively call the insert method on the left child and return the node that the recursive call creates.
  3. Otherwise, if item is greater than this.item, then do the same as Step 2 but instead go to the right of the current node.
README

This method is slightly different from our pseudocode during lecture. Here, we return the newly created node, whereas in lecture, we simply created the node but our insert method did not return anything. This only affects the return statements of the method, as described above.

Testing the Insert Method

After you’ve implemented the insert method, do not forget to create appropriate unit tests in your MyBinarySearchTreeNodeTest.java file. As suggestions, two tests could both create a root node, then (1) insert two items – one that should be to the left and one to the right, making sure the root is the parent of both (using the getParent method) and (2) try inserting the same item that is in the root and verify that null is returned by the insert method.

Committing Your Progress

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