Remove method and remove largest node from left subtree metods. Please finish the code so the JUnit Tester returns all passes. Here are the source codes. "XXX" means a new class.

public class BinarySearchTree {

private Node root;

public BinarySearchTree() {

root = null;

}

/*

* Adds the specified node to the BST

*/

public String add(String s) {

// root is a special case:

if (root == null) {

root = new Node(s);

return s;

}

Node current = root;

while (current != null) {

if (current.data.equals(s)) // no duplicates

return s;

else if (current.data.compareTo(s) > 0) { // go left

if (current.left == null) { // found nothing? Add node here

current.left = new Node(s);

} else {

current = current.left;

}

} else { // go right

if (current.right == null) { // found nothing? Add node here

current.right = new Node(s);

} else {

current = current.right;

}

}

}

return s;

}

/*

* Returns true if the string is found in the BST

*/

public boolean contains(String s) {

Node current = root;

while (current != null) {

if (current.data.equals(s))

return true;

if (current.data.compareTo(s) > 0) {

current = current.left;

} else {

current = current.right;

}

}

// Made it here? Not found!

return false;

}

/*

* Removes the specified string from the BST

*/

/*

* public boolean remove(String s) { Node pos = root;

*

* if (pos == null) { return false; }

*

* if (s.compareTo(pos.data) < 0) { pos = pos.left; remove(s); } else if

* (s.compareTo(pos.data) > 0) { pos = pos.right; remove(s); } else { if

* (pos.left != null && pos.right != null) { Node maxFromLeft =

* findMax(pos.left); pos.data = maxFromLeft.data; pos = pos.left;

* remove(maxFromLeft.data); } else if (pos.left != null) { pos = pos.left; }

* else if (pos.right != null) { pos = pos.right; } else { pos = null; } }

* return true; } // end remove method

*/

public boolean remove(String s) {

// if tree is empty

if (root == null) {

return false;

}

// if we find a match in the root

if (s.equals(root.data)) {

// if it is a leaf or has one child

if (root.left == null || root.right == null) {

root = root.left == null ? root.right : root.left;

}

// if root has 2 children

else {

Node maxLeft = max(root.left);

root.data = maxLeft.data;

maxLeft = null;

}

}

return false;

}

/**

* Find max in a tree

*

* @param node

* Root of the tree

* @return a Node with max

*/

private Node max(Node node) {

if (node == null)

return null;

while (node.right != null) {

node = node.right;

}

return node;

}

// Removes the largest node in the given tree,

// which will be the rightmost node, and returns

// the value from that node. The largest node

// will always have 0 or 1 children (if it had

// 2 children, then the right node would be larger).

private String removeLargestFromLeftSubtree(Node n) {

if (n.left == null) {

return n.data;

}

// return removeLargestFromLeftSubTree(n.right);

return null;

}

/*

* Prints the values in order

*/

public void inorderTraversal() {

inorderTraversal(root);

System.out.println();

}

/*

* Recursive helper for traversing

*/

private void inorderTraversal(Node n) {

if (n != null) {

inorderTraversal(n.left);

System.out.print(n.data + " ");

inorderTraversal(n.right);

}

}

/*

* Basic Binary Tree Node

*/

private class Node {

private String data;

private Node left, right;

private Node(String data) {

this.data = data;

left = right = null;

}

private Node getLeft() {

return left;

}

private Node getRight() {

return right;

}

}

}

XXXXXXXXXXXXXXXXXXXXXXX

import static org.junit.Assert.*;

import java.util.ArrayList;

import java.util.Collections;

import org.junit.Test;

public class JUnitBinarySearchTree {

@Test

public void testRemoveRoot() {

BinarySearchTree bst = new BinarySearchTree();

// Test removing from an empty tree:

assertFalse(bst.remove("cat"));

// Test removing root from a one-node tree:

bst.add("cat");

assertFalse(bst.remove("dog"));

assertTrue(bst.remove("cat"));

assertFalse(bst.remove("cat"));

// Test removing root from a tree where

// the root has exactly one child on the right:

bst.add("a");

bst.add("b");

assertFalse(bst.remove("c"));

assertTrue(bst.remove("a"));

assertFalse(bst.remove("a"));

// Test removing root from a tree where

// the root has exactly one child on the left:

bst.add("b");

bst.add("a");

assertFalse(bst.remove("c"));

assertTrue(bst.remove("b"));

assertFalse(bst.remove("b"));

}

@Test

public void testRemoveWithBigTree() {

ArrayList words = randomWordList(1000);

BinarySearchTree bst = new BinarySearchTree();

bst.add("This is the root");

for (int i = 0; i < words.size(); i++) {

bst.add(words.get(i));

}

assertTrue(bst.remove("This is the root"));

assertFalse(bst.remove("This is the root"));

Collections.shuffle(words);

while (!words.isEmpty()) {

String s = words.remove(0);

// Get rid of duplicates in the arraylist

while (words.contains(s))

words.remove(s);

bst.remove(s);

assertFalse(bst.contains(s));

for (int i = 0; i < words.size(); i++) {

assertTrue(bst.contains(words.get(i)));

}

}

}

public String randomWord(int length) {

String result = "";

while (result.length() < length) {

char c = (char)('a' + (int)(26 * Math.random()));

result += c;

}

return result;

}

public ArrayList randomWordList(int count) {

ArrayList result = new ArrayList<>();

while (result.size() < count) {

result.add(randomWord(4));

}

return result;

}

public boolean containsDuplicates(ArrayList list) {

for (int i = 0; i < list.size(); i++) {

for (int j = i + 1; j < list.size(); j++) {

if (list.get(i).equals(list.get(j))) {

return true;

}

}

}

return false;

}

}

XXXXXXXXXXXXXXXXXXXXXXXXX

public class Tester {

public static void main(String[] args) {

BinarySearchTree bst = new BinarySearchTree();

bst.add("house");

bst.add("mouse");

bst.add("cat");

bst.add("dog");

bst.add("cob");

bst.add("egg");

bst.inorderTraversal();

bst.remove("house");

bst.inorderTraversal();

bst.remove("mouse");

bst.inorderTraversal();

bst.remove("aa");

bst.inorderTraversal();

}

}