Implement methods for binary search trees:

Step 1: Start by writing a basic client program BinarySearchTreeDemo.java with the following skeletal structure:

public class BinarySearchTreeDemo{

public static void main(String[] args){

//create an empty binary search tree of Integer object

}

}

Step 2: To the Binary Search Tree class, add an instance method called findMax() that returns the largest key in the binary search tree.

public T findMax(){}

Note: The largest key is the rightmost node.

Step 3: To the Binary Search Tree class, add an instance method called findMin() that returns the smallest key in the binary search tree.

public T findMin(){}

Note: The smallest key is the leftmost node.

Step 4: The binary search tree class implements the search algorithm in a non-recursive manner. Implement a recursive search algorithm. Heres the outline of the solution:

//driver method

public BinaryTree recursiveSearch(T key) {

if (tree.isEmpty())

return null;

else

return recursiveSearch(tree, key);

}

//recursive search method

public BinaryTree recursiveSearch(BinaryTree t, T key) {

//complete the code

}

Step 5: Write a inorder traversal method in the BinarySearchTree.java class, so that you can traverse the BinarySearchTree. Remember this is a static method (take care while writing the header and while calling this method from another class).

Step 6: Write a findHeight method in the BinarySearchTree.java class so that you can find the height of the BinarySearchTree.

Step 7: Write a isHeightBalanced method in the BinarySearchTree.java class so that you can find if a BinarySearchTree is height balanced.

Step 8: Now go back to BinarySearchTreeDemo.java, and add code according to the following guidelines:

public class BinarySearchTreeDemo{

public static void main(String[] args){

//create an empty binary search tree of Integer object

//BLOCK 1:

//generate 10 random integers in the range 1 to 1000

//these are your keys

//insert these into the binary search tree

//do an inorder traversal and display the keys

//you should see that the keys are sorted

//display the minimum integer using the findMin method

//display the maximum integer using the findMax method

//prompt the user to search for a key

//use the recursive search method to search

//and display if the key was found or not

//BLOCK 2:

//generate 100 random integers (keys) in the range 1 to 1000

//create a binary search tree and insert the keys

//find the height of this tree and determine if this tree

//is height balanced.

//Repeat BLOCK 2 (tree with 100 nodes)

//50 times using a while loop

//Write the answers (height and if height balanced)

//into a text file.

}

}

update:

Thank you for looking at my problem!

//Binary Search Tree class //uses the Binary Tree class public class BinarySearchTree> //you are using the compareTo method on objects of type T; hence T should extend Comparable private BinaryTree tree; private int size; public BinarySearchTree() tree-new BinaryTree getTree() return tree; public boolean isEmpty() return tree.isEmpty); public int size() return size; public BinaryTree search(T key) BinaryTreeT t- tree; if (isEmpty)) return nul1; while (t!-null) if (key.compareTo(t.getData())e) else // key is found t-t.getLeft); t -t.getRight); return t; return null; public void insert (T item) BinaryTreeT> neMode newNode.setData(item); new BinaryTree(); //sets left, right, parent and data to null if (size0)treenewNode; size++;return; BinaryTree> //you are using the compareTo method on objects of type T; hence T should extend Comparable private BinaryTree tree; private int size; public BinarySearchTree() tree-new BinaryTree getTree() return tree; public boolean isEmpty() return tree.isEmpty); public int size() return size; public BinaryTree search(T key) BinaryTreeT t- tree; if (isEmpty)) return nul1; while (t!-null) if (key.compareTo(t.getData())e) else // key is found t-t.getLeft); t -t.getRight); return t; return null; public void insert (T item) BinaryTreeT> neMode newNode.setData(item); new BinaryTree(); //sets left, right, parent and data to null if (size0)treenewNode; size++;return; BinaryTree