I need to finish a Binary Search Tree class in java.(Just need to finish some methods inside.) The name of the class is BinarySearchTree.java.

I also have a BSTNode.java which creates the node in the BST.

Finally, I have a JUnit test file PublicBinarySearchTreeTest.java for you to test your code.

* My changes must NOT break the semantics of the methods.

* I may NOT change the signatures of the public methods, or add or remove public methods to the interface.

I WILL upvote if your codes pass the JUnit tests I provided. Thanks for your help.

Here is BinarySearchTree.java:

package structures;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Queue;

public class BinarySearchTree> implements BSTInterface {

protected BSTNode root;

public boolean isEmpty() {

return root == null;

}

public int size() {

return subtreeSize(root);

}

protected int subtreeSize(BSTNode node) {

if (node == null) {

return 0;

} else {

return 1 + subtreeSize(node.getLeft())

+ subtreeSize(node.getRight());

}

}

/**

* @return true if and only if the element is stored in the tree

* @throws NullPointerException if element is null

*/

public boolean contains(T t) {

// TODO

return false;

}

public boolean remove(T t) {

if (t == null) {

throw new NullPointerException();

}

boolean result = contains(t);

if (result) {

root = removeFromSubtree(root, t);

}

return result;

}

private BSTNode removeFromSubtree(BSTNode node, T t) {

// node must not be null

int result = t.compareTo(node.getData());

if (result < 0) {

node.setLeft(removeFromSubtree(node.getLeft(), t));

if (node.getLeft() != null) {

node.getLeft().setParent(node);

}

return node;

} else if (result > 0) {

node.setRight(removeFromSubtree(node.getRight(), t));

if (node.getRight() != null){

node.getRight().setParent(node);

}

return node;

} else { // result == 0

if (node.getLeft() == null) {

return node.getRight();

} else if (node.getRight() == null) {

return node.getLeft();

} else { // neither child is null

T predecessorValue = getHighestValue(node.getLeft());

node.setLeft(removeRightmost(node.getLeft()));

if (node.getLeft() != null) {

node.getLeft().setParent(node);

}

node.setData(predecessorValue);

return node;

}

}

}

private T getHighestValue(BSTNode node) {

// node must not be null

if (node.getRight() == null) {

return node.getData();

} else {

return getHighestValue(node.getRight());

}

}

private BSTNode removeRightmost(BSTNode node) {

// node must not be null

if (node.getRight() == null) {

return node.getLeft();

} else {

node.setRight(removeRightmost(node.getRight()));

if (node.getRight() != null){

node.getRight().setParent(node);

}

return node;

}

}

/**

* @return the element in the tree which .equals() the argument, or null if no such element exists

* @throws NullPointerException if element is null

*/

public T get(T t) {

// TODO

return null;

}

public void add(T t) {

if (t == null) {

throw new NullPointerException();

}

root = addToSubtree(root, new BSTNode(t, null, null));

}

protected BSTNode addToSubtree(BSTNode node, BSTNode toAdd) {

if (node == null) {

return toAdd;

}

int result = toAdd.getData().compareTo(node.getData());

if (result <= 0) {

node.setLeft(addToSubtree(node.getLeft(), toAdd));

if (node.getLeft() != null) {

node.getLeft().setParent(node);

}

} else {

node.setRight(addToSubtree(node.getRight(), toAdd));

if (node.getRight() != null){

node.getRight().setParent(node);

}

}

return node;

}

/**

* @return the least value stored in this tree, or null if the tree is empty

*/

public T getMinimum() {

// TODO

return null;

}

/**

* @return the greatest value stored in this tree, or null if the tree is empty

*/

public T getMaximum() {

// TODO

return null;

}

/**

* @return the height(levels) of the tree, or -1 if the tree is empty

*/

public int height() {

// TODO

return -2;

}

/**

* Returns an Iterator that performs a preorder traversal of the tree.

* The Iterator's behavior is not defined in the case that the tree is

* modified before the iteration is finished.

* @return an Iterator over the elements in preorder

*/

public Iterator preorderIterator() {

// TODO

return null;

}

public Iterator inorderIterator() {

Queue queue = new LinkedList();

inorderTraverse(queue, root);

return queue.iterator();

}

private void inorderTraverse(Queue queue, BSTNode node) {

if (node != null) {

inorderTraverse(queue, node.getLeft());

queue.add(node.getData());

inorderTraverse(queue, node.getRight());

}

}

/**

* Returns an Iterator that performs a postorder traversal of the tree.

* The Iterator's behavior is not defined in the case that the tree is

* modified before the iteration is finished.

* @return an Iterator over the elements in preorder

*/

public Iterator postorderIterator() {

// TODO

return null;

}

/**

* Returns true if and only if this tree and the other tree have the same

* structure, and equivalent values at each node. Uses equals() to check

* for node value equivalence.

* @return true if and only if the trees are structure- and value-equivalent

* @throws NullPointerException if other is null

*/

public boolean equals(BSTInterface other) {

// TODO

return false;

}

/**

* Returns true if and only if this tree and the other tree store the same

* values, regardless of structure. Uses equals() to check

* for stored value equivalence.

* @return true if and only if the trees are value-equivalent

* @throws NullPointerException if other is null

*/

public boolean sameValues(BSTInterface other) {

// TODO

return false;

}

/**

* Returns true if and only if the tree is completely balanced. A balanced

* tree is either a full tree, or a tree that would be full if all leaves in

* the highest level were removed.

* An empty tree is considered balanced.

* @return true if and only if the tree is balanced

*/

public boolean isBalanced() {

// TODO

return false;

}

/**

* Modifies the tree such that it is completely balanced.

* The modified tree must still obey the BST rule, and must contain the same

* values it did before it was balanced.

*/

public void balance() {

// TODO

}

public BSTNode getRoot() {

// DO NOT MODIFY

return root;

}

Here is BSTNode.java:

package structures;

public class BSTNode> implements BSTNodeInterface {

private T data;

private BSTNode left;

private BSTNode right;

private BSTNode parent;

public static final boolean RED = true;

public static final boolean BLACK = false;

private boolean color;

public BSTNode(T data, BSTNode left, BSTNode right) {

this.data = data;

this.left = left;

this.right = right;

parent = null;

}

public BSTNode(T data, BSTNode left, BSTNode right, boolean color) {

this.data = data;

this.left = left;

this.right = right;

this.color = color;

parent = null;

}

public T getData() {

return data;

}

public void setData(T data) {

this.data = data;

}

public boolean getColor() {

return color;

}

public void setColor(boolean color) {

this.color = color;

}

public BSTNode getLeft() {

return left;

}

public void setLeft(BSTNode left) {

this.left = left;

}

public BSTNode getRight() {

return right;

}

public void setRight(BSTNode right) {

this.right = right;

}

public BSTNode getParent() {

return parent;

}

public void setParent(BSTNode p) {

this.parent = p;

}

public void printSubtree(int spaces) {

if (right != null) {

right.printSubtree(spaces + 5);

}

for (int i = 0; i < spaces; i++) {

System.out.print(" ");

}

System.out.print(data);

System.out.print('-');

System.out.println(color);

if (left != null) {

left.printSubtree(spaces + 5);

}

}

}

Here is PublicBinarySearchTreeTest.java:

package structures;

import static org.junit.Assert.*;

import java.util.Iterator;

import java.util.concurrent.TimeUnit;

import org.junit.Rule;

import org.junit.Test;

import org.junit.Before;

import org.junit.rules.Timeout;

public class PublicBinarySearchTreeTest {

private BSTInterface emptyTree;

private BSTInterface oneNodeTree;

private static final String FOO = "foo";

@Rule

public Timeout timeout = new Timeout(1L, TimeUnit.SECONDS);

@Before

public void before() {

emptyTree = new BinarySearchTree();

oneNodeTree = new BinarySearchTree();

oneNodeTree.add(FOO);

}

@Test

public void testEmpty() {

assertTrue(emptyTree.isEmpty());

}

@Test

public void testNotEmpty() {

assertFalse(oneNodeTree.isEmpty());

}

@Test

public void testSize() {

assertEquals(0, emptyTree.size());

assertEquals(1, oneNodeTree.size());

}

@Test

public void testContains() {

assertTrue(oneNodeTree.contains(FOO));

}

@Test

public void testRemove() {

assertFalse(emptyTree.remove(0));

}

@Test

public void testGet() {

assertEquals(FOO, oneNodeTree.get(FOO));

}

@Test

public void testAdd() {

emptyTree.add(1);

assertFalse(emptyTree.isEmpty());

assertEquals(1, emptyTree.size());

}

@Test

public void testGetMinimum() {

assertEquals(null, emptyTree.getMinimum());

}

@Test

public void testGetMaximum() {

assertEquals(FOO, oneNodeTree.getMaximum());

}

@Test

public void testHeight() {

assertEquals(-1, emptyTree.height());

assertEquals(0, oneNodeTree.height());

}

@Test

public void testPreorderIterator() {

Iterator i = oneNodeTree.preorderIterator();

while (i.hasNext()) {

assertEquals(FOO, i.next());

}

}

@Test

public void testInorderIterator() {

Iterator i = oneNodeTree.inorderIterator();

while (i.hasNext()) {

assertEquals(FOO, i.next());

}

}

@Test

public void testPostorderIterator() {

Iterator i = emptyTree.postorderIterator();

assertFalse(i.hasNext());

}

@Test

public void testEquals() {

BSTInterface tree = new BinarySearchTree();

assertFalse(oneNodeTree.equals(tree));

tree.add(new String("foo"));

assertTrue(oneNodeTree.equals(tree));

}

@Test

public void testSameValues() {

BSTInterface tree = new BinarySearchTree();

assertTrue(emptyTree.sameValues(tree));

emptyTree.add(1);

emptyTree.add(2);

tree.add(2);

tree.add(1);

assertTrue(emptyTree.sameValues(tree));

}

@Test

public void testIsBalanced() {

// disabled due to late change of isBalanced() specification

// assertTrue(emptyTree.isBalanced());

emptyTree.add(1);

assertTrue(emptyTree.isBalanced());

emptyTree.add(2);

assertTrue(emptyTree.isBalanced());

emptyTree.add(3);

assertFalse(emptyTree.isBalanced());

}

@Test

public void testBalance() {

emptyTree.add(1);

emptyTree.add(2);

emptyTree.add(3);

assertFalse(emptyTree.isBalanced());

emptyTree.balance();

assertTrue(emptyTree.isBalanced());

}

}