Removing Items

As a final step in implementing the binary search tree data structure, we will implement a method for removing items from the tree. After this, we will have a fully functioning BST that we could use for different applications.

Find Successor Method

Before we can implement a method for removing an item from the tree, we first need to create a helper method that finds the node that is the successor of the current node in the BST. In your MyBinarySearchTreeNode<T> class, create a private method called findSuccessor that takes no parameters. The method should return the MyBinarySearchTreeNode<T> that contains the item that is the next biggest item in the BST. Recall from lecture that the pseudocode for this method is:

1. First, navigate to the rightChild (since the next biggest item must be to the right of the current node)
2. Continue following the leftChild of the right subtree until there are no more children to the left.
3. Return the last leftChild encountered in Step 2.

Remove Method

Finally, create a public method called remove that returns nothing and takes as a single parameter an item of type T. Recall from lecture and our reading that the remove method works recursively:

1. First compare the current node’s this.item with the argument item. If they are the same, we need to remove the current node:

• If the current node is a leaf, we check whether it is the left or right child of its parent, then we assign that child to be null in the parent
• If the current node has only one child, then we again check whether the current node is the left or right child of its parent, then we reassign that child in the parent to be the current node’s only child. This promotes the current node’s only child up one level of depth in the BST.
• If the current node has two children, then we first find the successor of the current node using the findSuccessor method implemented above. Then, we save the successor node’s item, remove the successor node from the tree (by calling the remove method with the successor node’s item as the argument, and finally replace the current node’s item with the successor node’s item.

2. If item is less than this.item, then item should have been stored somewhere to the left of the current node. If the current node has a left child, recursively call the remove method on the left child with the same item argument. If the current node does not have a left child, then item is not in the tree and we do not need to remove anything, so go ahead and return from the method.
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.

Testing Our Remove Method

Before moving on, create several unit tests verifying that your remove method was implemented properly. It is the most complicated method of this assignment, so it might take a little time to debug.

Some suggested test cases for your unit tests:

1. Try removing leaf nodes that are a left child of their parent and a right child of their parent
2. Try removing nodes that have a single child on either side of the node to remove. Try to also remove single child nodes that are themselves a left child of their parent and a right child of their parent
3. Try removing a node that has two children and the successor node is a leaf
4. Try removing a node that has two children and the successor node itself has one child

Committing Your Progress

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