Step 1: Rewrite the inorder traversal method in the BinarySearchTree.java class, so that you can traverse the BinarySearchTree. Remember this is a static method.

Step 2: Rewrite the findHeight method in the BinarySearchTree.java class so that you can find the height of the BinarySearchTree. Step 3: Rewrite the isHeightBalanced method in the BinarySearchTree.java class so that you can find if a BinarySearchTree is height balanced.

step 4: 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. } } public class BinaryTree { private T data; private BinaryTree parent; private BinaryTree left; private BinaryTree right; public BinaryTree() { parent = left = right = null; data = null; } public void makeRoot(T data) { if (!isEmpty()) { System.out.println("Can't make root. Already exists"); } else this.data = data; } public void setData(T data) { this.data = data; } public void setLeft(BinaryTree tree) { left = tree; } public void setRight(BinaryTree tree) { right = tree; } public void setParent(BinaryTree tree) { parent = tree; } public T getData() { return data; } public BinaryTree getParent() { return parent; } public BinaryTree getLeft() { return left; } public BinaryTree getRight() { return right; } public void attachLeft(BinaryTree tree) { if (tree==null) return; else if (left!=null || tree.getParent()!=null) { System.out.println("Can't attach"); return; } else { tree.setParent(this); this.setLeft(tree); } } public void attachRight(BinaryTree tree) { if (tree==null) return; else if (right!=null || tree.getParent()!=null) { System.out.println("Can't attach"); return; } else { tree.setParent(this); this.setRight(tree); } } public BinaryTree detachLeft() { if (this.isEmpty()) return null; BinaryTree retLeft = left; left = null; if (retLeft!=null) retLeft.setParent(null); return retLeft; } public BinaryTree detachRight() { if (this.isEmpty()) return null; BinaryTree retRight = right; right =null; if (retRight!=null) retRight.setParent(null); return retRight; } public boolean isEmpty() { if (data == null) return true; else return false; } public void clear() { left = right = parent =null; data = null; } public BinaryTree root() { if (parent == null) return this; else { BinaryTree next = parent; while (next.getParent()!=null) next = next.getParent(); return next; } } public static  void preorder(BinaryTree t) { if (t!=null) { System.out.print(t.getData()+"\t"); preorder(t.getLeft()); preorder(t.getRight()); } } public static  void inorder(BinaryTree t) { if (t!=null) { inorder(t.getLeft()); System.out.print(t.getData() + "\t"); inorder(t.getRight()); } } public static  void postorder(BinaryTree t) { if (t!=null) { postorder(t.getLeft()); postorder(t.getRight()); System.out.print(t.getData() + "\t"); } } }

//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();

size=0;

}

public BinaryTree getTree()

{

return tree;

}

public boolean isEmpty()

{

return tree.isEmpty();

}

public int size()

{

return size;

}

public BinaryTree search(T key)

{

BinaryTree t = tree;

if (isEmpty()) return null;

while (t!=null)

{

if (key.compareTo(t.getData())<0)

t = t.getLeft();

else if (key.compareTo(t.getData())>0)

t = t.getRight();

else // key is found

return t;

}

return null;

}

public void insert(T item)

{

BinaryTree newNode = new BinaryTree(); //sets left, right, parent and data to null

newNode.setData(item);

if (size==0){tree = newNode; size++;return;}

BinaryTree t = tree;

boolean done = false;

while (!done)

{

int c = item.compareTo(t.getData());

if (c==0)

{

System.out.println("Duplicate key. Can't insert");

return;

}

else if (c<0) //need to go left

{

if (t.getLeft()==null) //place to insert found

{

t.setLeft(newNode);

newNode.setParent(t);

size++;

done = true;

}

else

t = t.getLeft(); //otherwise go left one branch

}

else //c>0; need to go right

{

if (t.getRight()==null) //place to insert found

{

t.setRight(newNode);

newNode.setParent(t);

size++;

done=true;

}

else

t = t.getRight();

}

}

}

public BinaryTree findPredecessor(BinaryTree node)

{

if (node==null) return null;

if (node.getLeft()==null) return null;

BinaryTree pred = node.getLeft();

while (pred.getRight()!=null)

pred = pred.getRight();

return pred;

}

public void deleteHere(BinaryTree deleteNode, BinaryTree attach)

{

if (deleteNode==null) return;

BinaryTree parent = deleteNode.getParent();

if (parent == null) return;

if (attach == null)

{

if (parent.getLeft()==deleteNode)

parent.setLeft(null);

else

parent.setRight(null);

return;

}

if (deleteNode==parent.getRight())

{

parent.detachRight();

deleteNode.setParent(null);

//attach.setParent(parent);

attach.setParent(null);

parent.attachRight(attach);

attach.setParent(parent);

}

else

{

parent.detachLeft();

deleteNode.setParent(null);

//attach.setParent(parent);

attach.setParent(null);

parent.attachLeft(attach);

attach.setParent(parent);

}

deleteNode.clear();

}

public void delete(T key)

{

if (size==0){System.out.println("Can't delete. Empty tree"); return;}

BinaryTree deleteNode = search(key);

if (deleteNode==null) {System.out.println("Key not found. Can't delete"); return;}

BinaryTree hold = null;

if (deleteNode.getLeft()==null && deleteNode.getRight()==null)

{

deleteHere(deleteNode, null);

}

else if (deleteNode.getLeft()==null)

{

hold = deleteNode.getRight();

deleteHere(deleteNode, hold);

}

else if (deleteNode.getRight()==null)

{

hold = deleteNode.getLeft();

deleteHere(deleteNode, hold);

}

else

{

hold = findPredecessor(deleteNode);

deleteNode.setData(hold.getData());

deleteNode=hold;

deleteHere(deleteNode, deleteNode.getLeft());

}

size--;

}

}