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.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--; } } 

This lab requires you to add/modify methods in the BinarySearchTree class. Test all the methods in a client program (BinarySearchTreeDemo.java). Do not hardcode any of the input values in your source code. Prompt the user to enter the values. Exercise 1: In the binary search tree class, write a method called findMax(0 that returns the largest key in the binary search tree. Test the method in BinarySearchTreeDemo.java. public T findMax() Note: The largest key is the rightmost node. that returns the smallest key in the Exercise 2: In the binary search tree class, write a method called findMin binary search tree. Test the method in BinarySearchTreeDemo.java. public T findMin..) Note: The smallest key is the leftmost node Exercise 3: The binary search tree class implements the search algorithm in a non-recursive manner Implement a recursive search algorithm. Test the method in BinarySearchTreeDemo.java. Here's 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 Exercise 4: Given a binary tree, write a method that determines whether the tree is a binary search tree. Test it using a driver (main) program. public boolean isBinarySearchTree (BinaryTree t)