In the BinarySearchTree class, write the new method: private E deletePredecessor(BSTNode where) This method should find and delete the in-order predecessor of where, returning the value that was deleted. If where itself is null, or if where doesn’t have a predecessor (i. e., the left subtree doesn’t exist), the method should return null. The method is declared private since it’s meant to be called only from another method of BinarySearchTree, to be written later.
In the BinarySearchTree class, write the new method: private E deleteSuccessor(BSTNode where)
This method should find and delete the in-order successor of where, returning the value that was deleted. If where itself is null, or if where doesn’t have a successor (i. e., the right subtree doesn’t exist), the method should return null. The method is declared private since it’s meant to be called only from another method of BinarySearchTree, to be written later.
In the BinarySearchTree class, write the new method: public E remove(E item)
This method should find and delete the item from the BST, returning the value that was re- moved. If the item is not found in the tree, the method should leave the tree unchanged and return null. Use the pseudocode in Figure 9.6.1 of the zyBook as a starting point. However, when removing a node with two children, your code should randomly select whether to use the in-order predecessor or successor in the delete algorithm. This will prevent the tree from get- ting too unbalanced. Call your previously written deletePredecessor and deleteSuccessormethods as needed.
In the BinarySearchTree class, write a main method that tests your removemethod. Be sure to test at least four cases:
• Removing a node with no children
• Removing a node with only a left child
• Removing a node with only a right child
• Removing a node with two children
BinarySearchTree
public class BinarySearchTree< E extends Comparable> {
// Maintains the root (first node) of the tree
private BSTNode root;
// Adds the newValue to the BST
// This method also prevents duplicate values from being added to the BST.
public void add(E newValue) {
// Create a new BSTNode that contains the newValue
BSTNode newNode = new BSTNode<>(newValue, null, null);
// If tree is empty, the newNode should become the root
if (root == null)
root = newNode;
else {
BSTNode currentNode = root;
while (currentNode != null) {
// Compare the newValue vs. the data in the currentNode
int compareResult = newValue. compareTo(currentNode. getData());
// newValue is "less than" the current node - go left
if (compareResult < 0) {
// If there is no left child for currentNode, make newNode
// the left child of currentNode
if (currentNode. getLeft() == null) {
currentNode. setLeft(newNode);
currentNode = null;
}
// If there *is* a left child for currentNode, just move
// currentNode down the left subtree
else
currentNode = currentNode. getLeft();
}
// newValue is "greater than" the current node - go right
else if (compareResult > 0) {
// If there is no right child for currentNode, make newNode
// the right child of currentNode
if (currentNode. getRight() == null) {
currentNode. setRight(newNode);
currentNode = null;
}
// If there *is* a right child for currentNode, just move
// currentNode down the right subtree
else
currentNode = currentNode. getRight();
}
// newValue is "equal to" the current node - exit the loop without adding newValue
else
currentNode = null;
}
}
}