In the class LinkedBinarySearchTree implement only the following methods:

removeMax

findMin

findMax

import java.util.NoSuchElementException; public class LinkedBinarySearchTree> extends LinkedBinaryTree implements BinarySearchTree { /** * Creates an empty binary search tree. */ public LinkedBinarySearchTree() { super(); }

/** * Creates a binary search with the specified element as its root. * * @param element the element that will be the root of the new binary * search tree */ public LinkedBinarySearchTree(E element) { super(element); } @Override public void add(E element) { if (isEmpty()) { // Add as root of new tree root = new LinkedBinaryTreeNode(element); modCount += 1; } else if (element.compareTo(root.element) < 0) { // Add to left subtree if (root.left == null) { root.left = new LinkedBinaryTreeNode(element); } else { add(element, root.left); } modCount += 1; } else if (0 < element.compareTo(root.element)){ // Add to right subtree if (root.right == null) { root.right = new LinkedBinaryTreeNode(element); } else { add(element, root.right); } modCount += 1; } else { // Element found in tree. Do not add to tree. } } private void add(E element, LinkedBinaryTreeNode node) { if (element.compareTo(node.element) < 0) { // Add to left subtree if (node.left == null) { node.left = new LinkedBinaryTreeNode(element); } else { add(element, node.left); } } else if (0 < element.compareTo(node.element)) { // Add to right subtree if (node.right == null) { node.right = new LinkedBinaryTreeNode(element); } else { add(element, node.right); } } else { // Element found in tree. Do not add to tree. } } @Override public E remove(E targetElement) { if (isEmpty()) { throw new NoSuchElementException("LinkedBinarySearchTree"); }

E result = null;

LinkedBinaryTreeNode parent = null; if (targetElement.equals(root.element)) { // Target element found result = root.element; LinkedBinaryTreeNode temp = replacement(root); if (temp == null) { root = null; } else { root.element = temp.element; root.right = temp.right; root.left = temp.left; }

modCount -= 1; } else { // Target element not found parent = root; if (targetElement.compareTo(root.element) < 0) { result = removeElement(targetElement, root.left, parent); } else { result = removeElement(targetElement, root.right, parent); } }

return result; } private E removeElement(E targetElement, LinkedBinaryTreeNode node, LinkedBinaryTreeNode parent) { if (node == null) { throw new NoSuchElementException("LinkedBinarySearchTree"); } E result = null;

if (targetElement.equals(node.element)) { // Target element found. result = node.element; LinkedBinaryTreeNode temp = replacement(node); if (parent.right == node) { parent.right = temp; } else { parent.left = temp; }

modCount -= 1; } else { // Target element not found parent = node; if (targetElement.compareTo(node.element) < 0) { // Look in left subtree result = removeElement(targetElement, node.left, parent); } else { // Look in right subtree result = removeElement(targetElement, node.right, parent); } }

return result; } private LinkedBinaryTreeNode replacement(LinkedBinaryTreeNode node) { LinkedBinaryTreeNode result = null;

if ((node.left == null) && (node.right == null)) { // No children result = null; } else if ((node.left != null) && (node.right == null)) { // Left child only result = node.left; } else if ((node.left == null) && (node.right != null)) { // Right child only result = node.right; } else { // Two children // Find leftmost descendant of right subtree LinkedBinaryTreeNode parent = node; LinkedBinaryTreeNode cursor = node.right; while (cursor.left != null) { parent = cursor; cursor = cursor.left; }

// Restructure the tree cursor.left = node.left; if (node.right != cursor) { parent.left = cursor.right; cursor.right = node.right; }

result = cursor; }

return result; } @Override public E removeMin() { if (isEmpty()) { throw new IllegalStateException("LinkedBinarySearchTree"); }

E result = null;

if (root.left == null) { // Minimum element is the root result = root.element; root = root.right; } else { // Minimum element is in the left subtree // Find leftmost descendant of left subtree LinkedBinaryTreeNode parent = root; LinkedBinaryTreeNode cursor = root.left; while (cursor.left != null) { parent = cursor; cursor = cursor.left; } result = cursor.element; // Restructure the tree parent.left = cursor.right; }

modCount -= 1;

return result; } @Override public E removeMax() { // To be implemented. } @Override public E findMin() { // To be implemented. } @Override public E findMax() { // To be implemented. } }