I need to finish a binary search tree class called BST.java. There are two methods which I need to work on: search() and isValid().

I may NOT use any recursion. I MUST use loops.

I have three java files: One is the BST.java which I need to work on; One is the BSTNode.java which create the node; One is a JUnit test file RunTests.java.

I WILL rate if your code passes the JUnit tests I provided. Hope you can help.

Here is BST.java:

package binary_search;

import java.util.ArrayList;

public class BST> {

private BSTNode root;

public BST() {

root = null;

}

public BST(BSTNode root) {

this.root = root;

}

public BST(T[] sorted) {

/* This constructor builds a BST from a sorted array */

root = sortedArrayToBST(sorted, 0, sorted.length-1);

}

/* TODO: implement an iterative method (i.e. using a loop) that searches

* for a element in the BST. In lecture slides we covered a recursive version.

* Here you must implement it using a loop and no recursion.

* Return null if the element does not exist; or the node containing

* the element if it exists.

* Remember: for generic type T, you cannot use < or >, instead

* you must use the compareTo or equals method.

*/

public BSTNode search(T elem) {

return null;

}

/* TODO: implement a method that checks whether this is a valid BST.

* There are at least two solutions. You can implement either. You

* are allowed to use recursion for this question. If you create any

* new method, you must include it in the written document.

*

* In the first solution, perform an in-order traversal and save the

* traversed elements in a Java ArrayList, then use the ArrayList to help you

* check whether this is a valid BST or not (think about how).

* This solution is easy to implement but requires O(N) memory.

*

* In the second solution, you can avoid using additional memory such as

* an ArrayList. Instead, make use of the definition of a BST to implement

* the validity checking. Hint: during recursion, you can pass minimum and

* maximum values down to the recursive calls to help you track what's the

* allowed range of values of the children node. Alternatively, you can have

* the recursive method return the minimum and maximum values of each subtree,

* and use those values to track the allowed range of values of the the parent.

*/

public boolean isValid() {

return true;

}

/* YOU DO NOT NEED TO MODIFY ANY CODE BELOW THIS LINE */

private BSTNode sortedArrayToBST(T array[], int start, int end) {

if (start>end) return null; // if the range has crossed over

int mid = (start+end)/2; // find middle element

BSTNode node = new BSTNode(array[mid]); // construct node

node.left = sortedArrayToBST(array, start, mid-1); // recursively build left subtree

node.right= sortedArrayToBST(array, mid+1, end); // recursively build right subtree

return node;

}

public int size() {

return sizeHelper(root);

}

private int sizeHelper(BSTNode node) {

if(node==null) return 0;

return 1+sizeHelper(node.left)+sizeHelper(node.right);

}

}

Here is BSTNode.java:

package binary_search;

public class BSTNode> {

public T data;

public BSTNode left;

public BSTNode right;

public BSTNode() {

this(null, null, null);

}

public BSTNode(T data) {

this(data, null, null);

}

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

this.data = data;

this.left = left;

this.right = right;

}

}

Here is the JUnit test file RunTests.java:

package binary_search;

import java.util.Arrays;

import java.util.Random;

public class RunTests {

public static void main(String[] args) {

System.out.println("====== Test BST search and performance ======");

testBSTSearch();

System.out.println(" ====== Test BST validity ======");

testValidBST();

}

public static String searchResult(BST bst, Integer elem) {

return (bst.search(elem)==null)?"it does NOT exist":"it exists";

}

public static void testValidBST() {

BST bst = new BST();

System.out.println("An empty tree is valid BST, and your answer is: " + bst.isValid());

bst = new BST(new BSTNode(10));

System.out.println("A tree with only a root is valid BST, and your aoswer is: " + bst.isValid());

BSTNode test1 = new BSTNode(10);

test1 = new BSTNode(12, test1, null);

test1 = new BSTNode(8, null, test1);

test1 = new BSTNode(7, null, test1);

BSTNode left = new BSTNode(1);

BSTNode right = new BSTNode(5);

left = new BSTNode(2, left, right);

test1.left = left;

bst = new BST(test1);

System.out.println("test1.isValid() should be true, and your answer is " + bst.isValid());

BSTNode test2 = new BSTNode(10);

test2 = new BSTNode(15, test2, null);

test2 = new BSTNode(12, null, test2);

test2 = new BSTNode(6, null, test2);

left = new BSTNode(1);

right = new BSTNode(5);

left = new BSTNode(2, left, right);

test2.left = left;

bst = new BST(test2);

System.out.println("test2.isValid() should be false, and your answer is " + bst.isValid());

BSTNode test3 = new BSTNode(10);

test3 = new BSTNode(12, test3, null);

test3 = new BSTNode(8, null, test3);

test3 = new BSTNode(6, null, test3);

left = new BSTNode(1);

right = new BSTNode(7);

left = new BSTNode(2, left, right);

test3.left = left;

bst = new BST(test3);

System.out.println("test3.isValid() should be false, and your answer is " + bst.isValid());

}

public static void testBSTSearch() {

// Test BST search

// Create random number array

final int N = 1000000;

Integer[] elements = new Integer[N];

Integer[] sorted = new Integer[N];

Random rng = new Random(); // random number generator

for(int i=0;i

elements[i] = rng.nextInt();

sorted[i] = elements[i];

}

Arrays.sort(sorted);

BST bst = new BST(sorted);

// Test searching for K numbers

final int K = 500;

System.out.println("Test search correctness 1");

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

Integer target = elements[i]; // any element in the random array should exist

if(bst.search(target)==null) {

System.out.println("Failed!!!");

return;

}

}

System.out.println("Passded");

System.out.println("Test search correctness 2");

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

Integer target = rng.nextInt();

// test random numbers and consistency between linear search and BST search

if(linearSearch(elements, target) != (bst.search(target)!=null)) {

System.out.println("Failed!!!");

return;

}

}

System.out.println("Passded");

long tStart, tEnd, tDelta;

double elapsedSeconds;

System.out.println("Linear search for " + K + " numbers started...");

tStart = System.currentTimeMillis();

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

linearSearch(elements, rng.nextInt());

}

tEnd = System.currentTimeMillis();

tDelta = tEnd - tStart;

elapsedSeconds = tDelta / 1000.0;

System.out.println("Finished in " + elapsedSeconds + " second.");

System.out.println("BST search for " + K + " numbers started...");

tStart = System.currentTimeMillis();

for (int i = 1; i < 1000; i++) {

bst.search(rng.nextInt());

}

tEnd = System.currentTimeMillis();

tDelta = tEnd - tStart;

elapsedSeconds = tDelta / 1000.0;

System.out.println("Finished in " + elapsedSeconds + " second.");

}

// linear search in an unsorted array

private static boolean linearSearch(Integer[] array, Integer target) {

for(int i=0;i

if(array[i].equals(target)) return true;

}

return false;

}

}