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.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 (c0; 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())

import java.util.ArrayList; public class BinaryTree parent private BinaryTreeT> left; private BinaryTree right; public BinaryTree) ( parent left right null; datanull; public void makeRoot (T data) ( if (isEmpty)) System.out.println("Can't make root. Already exists"; else this. datadata; public void setData(T data) this.datadata; public void setLeft(BinaryTree tree) t left tree; public void setRight (BinaryTree tree) t right tree; public void setParent (BinaryTreeT> tree) f parenttree; public T getData) f return data; public BinaryTree getParent) return parent public BinaryTreeT> getLeft) t return left; public BinaryTree getRight) return right; public void attachLeft (BinaryTree tree) ( if (tree null) return else if (left|-null l tree.get Parent() !=null) { System.out.println("Can't attach") return; else tree.setParent (this); this.setLeft (tree); public void attachRight (BinaryTree tree) if (tree:-nul1) return; else if (right! null |I tree.getParent()!-nul1) { System.out.println("Can't attach); return else f tree.setParent (this); this.setRight (tree); public BinaryTreeT> detachLeft) if (this.isEmpty)) return null; BinaryTree retLeftleft; left -null; if (retLeftl null) retLeft.setParent (null); return retLeft; import java.util.ArrayList; public class BinaryTree parent private BinaryTreeT> left; private BinaryTree right; public BinaryTree) ( parent left right null; datanull; public void makeRoot (T data) ( if (isEmpty)) System.out.println("Can't make root. Already exists"; else this. datadata; public void setData(T data) this.datadata; public void setLeft(BinaryTree tree) t left tree; public void setRight (BinaryTree tree) t right tree; public void setParent (BinaryTreeT> tree) f parenttree; public T getData) f return data; public BinaryTree getParent) return parent public BinaryTreeT> getLeft) t return left; public BinaryTree getRight) return right; public void attachLeft (BinaryTree tree) ( if (tree null) return else if (left|-null l tree.get Parent() !=null) { System.out.println("Can't attach") return; else tree.setParent (this); this.setLeft (tree); public void attachRight (BinaryTree tree) if (tree:-nul1) return; else if (right! null |I tree.getParent()!-nul1) { System.out.println("Can't attach); return else f tree.setParent (this); this.setRight (tree); public BinaryTreeT> detachLeft) if (this.isEmpty)) return null; BinaryTree retLeftleft; left -null; if (retLeftl null) retLeft.setParent (null); return retLeft