Your Task: Your task will be to create the following method: private TreeNode remove(TreeNode curr, E data). This method, like the other methods, will be called via its publicly accessible wrapper method. This method should recursively look for the node we want to remove and, if such a node is found, remove it using the psudeocode above: Step 1 (red): Here we are recurring down the tree to search for the node we want to remove. Step 2: Remove using cases o Case 1 (green): No sub-tree. o Case 2 (blue): One sub-tree. o Case 3 (purple): Both sub-trees. A description of each situation and how the above psudeocode addresses that situation is below. Removing a leaf The removal of a leaf is perhaps the most straightforward operation. In the event that both the right and the left points of a node are null then we only need to remove the reference from that nodes parent to it.

The second case, where the node we want to remove has a right or left sub-tree. As with the first step, we begin by finding the node we want to remove and its parent (Figure 9). We then take the right pointer of the parent and skip over the node we are removing from the tree by updating it to point to root of the node we want to removes existing sub-tree (Figure 10). A similar approach is used if the node we want to remove only has one sub-tree to the left. In that case, we modify the left pointer of the parent to skip over the node we are removing. Removing a node with two sub-trees The process of removing a node that has two sub-trees begins with finding the node we want to remove (Figure 11). We then have to find the minimum node in the node we want to removes right sub-tree; otherwise known as the node we want to removes inorder successor. At this point the most straightforward option to remove the orange node is to copy the data from the inorder successor node (Figure 13). Finally, we make a recursive call to the remove method to remove the successor node so that the duplicate we created is no longer in the tree.

this is the starter code:

public class BinarySearchTree> { private static class TreeNode> { E data; TreeNode left; TreeNode right; public TreeNode(E data) { this.data = data; left = null; right = null; } @Override public String toString() { return data.toString(); } } private TreeNode root; private int currentSize; public BinarySearchTree() { root = null; currentSize = 0; } public void add(E data) { root = add(root, data); } private TreeNode add(TreeNode curr, E data) { return new TreeNode<>(null); // Remove when you code this method } public boolean contains(E data) { return search(root, data) != null; } public TreeNode search(TreeNode curr, E data) { return new TreeNode<>(null); // Remove when you code this method } public void remove(E data) { root = remove(root, data); } private TreeNode remove(TreeNode curr, E data) { return new TreeNode<>(null); // Remove when you code this method } public E minimum(){ if (root == null) { return null; } return findMinNode(root).data; }

private TreeNode findMinNode(TreeNode curr) { return new TreeNode<>(null); // Remove when you code this method } /* Inorder Traversal */ public void traverseInOrder() { System.out.print("Inorder Traversal: "); traverseInOrder(root); System.out.println(); } private void traverseInOrder(TreeNode curr) { return; // Remove when you code this method } /* Preorder Traversal */ public void traversePreOrder() { System.out.print("Preorder Traversal: "); traversePreOrder(root); System.out.println(); } private void traversePreOrder(TreeNode curr) { return; // Remove when you code this method } /* Post Order Traversal */ public void traversePostOrder() { System.out.print("Postorder Traversal: "); traversePostOrder(root); System.out.println(); } private void traversePostOrder(TreeNode curr) { return; // Remove when you code this method } public int size() { return currentSize; }