Exercise 1: In the binary search tree class, write a method called findMax() 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.

Exercise 2: In the binary search tree class, write a method called findMin() that returns the smallest key in the 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. 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

}

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)

Binary Tree Class

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"); } } } 

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