Now got back to BinarySearchTreeDemo.java, and add the code according to the follwoing 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. }

}

//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--; } public T findMin() { if(tree.isEmpty()) return null; BinaryTree t = tree; while(t.getLeft() != null) t = t.getLeft(); return t.getData(); } public T findMax() { if(tree.isEmpty()) return null; BinaryTree t = tree; while(t.getRight() != null) t = t.getRight(); return t.getData(); } public BinaryTree recursiveSearch(T key){ if(tree.isEmpty()) return null; else return recursiveSearch(tree, key); } public BinaryTree recursiveSearch(BinaryTree t, T key){ if(t.getData().equals(key)) return t; else if(key.compareTo(t.getData()) < 0) return recursiveSearch(t.getLeft(), key); else return recursiveSearch(t.getRight(), key); } public static void inorder(BinaryTree t) { if (t!=null) { inorder(t.getLeft()); System.out.print(t.getData() + "\t"); inorder(t.getRight()); } } public int getHeight() { if(tree.getLeft() != null && tree.getRight() != null) return 1 + Math.max(tree.getLeft().getHeight(), tree.getRight().getHeight()); else if(tree.getLeft() != null) return 1 + tree.getLeft().getHeight(); else if (tree.getRight() != null) return 1 + tree.getRight().getHeight(); else return 0; } public boolean balanced() { boolean balanced = false; if(tree.getLeft().getHeight() == tree.getRight().getHeight() || tree.getLeft().getHeight() + 1 == tree.getRight().getHeight() || tree.getLeft().getHeight() - 1 == tree.getRight().getHeight()) balanced = true; return balanced; } }