//binary search tree 

class BST implements SearchStructure {
  protected TreeCell t;
  protected TreeCell finger;//a cursor into the data structure
  protected TreeCell previous;//previous is one step behind finger
  protected int size;

  public BST() {
    t = null;
    size = 0;
  }

  public String toString() {
    return "Tree has " + size + " elements:" + t;
  }

  public int size() {
    return size;
  }

    public boolean search(Object o){
	finger = t;
	previous = null;

	while (finger != null) {
	    int test = ((Comparable)finger.getDatum()).compareTo(o);
	    if (test == 0) return true;
	    //need to explore one of the subtrees
	    //set up the cursors correctly
	    previous = finger;
	    if (test < 0)
		//explore right subtree
		finger = finger.getRight();
	    else 
		//explore left subtree
		finger = finger.getLeft();	    
	}
        return false;
    }

  public void insert (Object o)  {
    if (t == null){//empty tree
      t = new TreeCell(o);
      size = size + 1;
      return;
    }
    //non-empty tree:look for object first, setting up cursors
    boolean found = search(o);
    if (! found) {//previous points to last TreeCell on path from root
      //put o into a child of previous
      int test = ((Comparable)previous.getDatum()).compareTo(o);
      if (test < 0)
	previous.setRight(new TreeCell(o));
      else  
	previous.setLeft(new TreeCell(o));
      size = size + 1;
    }
  }

  //returns maximum value in tree rooted at parameter t
  //if the maximum value is at root of t, t is not changed
  //otherwise, the maximum value is spliced out of the subtree rooted at t
  public Comparable extractMax(TreeCell t) {
    if (t == null) return null;
    //set up cursors
    finger = t;
    previous = null;
    Comparable maxVal = myExtractMax(t);
    return maxVal;
  }

  //helper method
  protected Comparable myExtractMax(TreeCell t){
    //assume t is non-null
    if (t.getRight() == null) {
      //t is rightmost node
      //splice out t
      if (previous != null) 
	previous.setRight(finger.getLeft());
      return (Comparable) (t.getDatum());
    }
    else {
      previous = finger;
      finger = t.getRight();
      return myExtractMax(finger);
    }
  }

 public void delete(Object o) {
  boolean found = search(o);
  if (! found) return;
  //check if left subtree of finger cell is null
  size = size - 1;
  if (finger.getLeft() == null) 
    //if so, easy to short out finger cell
    if (previous == null)
      //deleting root node of tree 
       t = finger.getRight(); 
    else {
      //deleting some internal node of tree
       if (previous.getLeft() == finger)
         //finger is to the left of previous
         previous.setLeft(finger.getRight());
       else
         //finger is to the right of previous
         previous.setRight(finger.getRight());
    }
  else {
    //there is a non-trivial subtree to left of updatedCell
    TreeCell updatedCell = finger; //delete from this cell
    TreeCell leftSubtree = finger.getLeft();
    if (leftSubtree.getRight() == null) {//root of leftSubtree has max
      //splice out root of leftSubtree
      finger.setDatum(leftSubtree.getDatum());
      finger.setLeft(leftSubtree.getLeft());
      return;
    }
    else {
      Comparable maxValue = extractMax(leftSubtree); 
      updatedCell.setDatum(maxValue);
    }
  }
 }
}


class testBST {

  public static void main(String[] args) {
    BST t = new BST();
    t.insert("Hillary");
    t.insert("Bill");
    t.insert("Monica");
    t.insert("Gennifer");
    t.insert("Ingrid");
    System.out.println(t);
    System.out.println(t.search("Bill"));
    System.out.println(t.search("Gennifer"));
    System.out.println(t.search("Monica"));
    t.delete("Hillary");
    System.out.println(t);
    System.out.println(t.search("Hillary"));
    t.delete("Bill");
    System.out.println(t);
    t.delete("Ingrid");
    System.out.println(t);
    t.delete("Monica");
    System.out.println(t);
    t.delete("Gennifer");
    System.out.println(t);
  }
}

//some auxiliary functions for checking if tree is a BST
//and returning max value stored in a BST
class junk {

    public static Object getMax(TreeCell t) {
	if (t == null) return null;
        if (t.getRight() == null)//t is it
	    return t.getDatum();
        else 
	    return getMax(t.getRight());
    }

    //This method checks if a tree is a BST
    public static boolean isBST(TreeCell t) {
	return minMaxBST(t).isBST;
    }

    //returns a triplet containing <boolean,low,hi>
    //boolean is true if parameter is a BST
    //low and he are the lowest and highest objects in BST 
    public static Triplet minMaxBST(TreeCell t) {
	Triplet left,right;
	if (t == null) 
	    return new Triplet(true,null,null);

	//non-null t
        Object nodeValue = t.getDatum();
	if (t.getLeft() != null) 
	    left = minMaxBST(t.getLeft());
	else //left subtree missing, so return a dummy triplet
	    left = new Triplet(true,(Comparable)nodeValue,(Comparable)nodeValue);
        if (t.getRight() != null)
	    right = minMaxBST(t.getRight());
	else //right subtree missing so return a dummy subtree
	    right = new Triplet(true,(Comparable)nodeValue,(Comparable)nodeValue);

	//if leftsubtree is a BST and rightsubtree is a BST
	//and max value in left subtree is <= value in node
	//and min value in right subtree is >= value in node
	//we have a BST!
 	boolean isBST = left.isBST && right.isBST 
	    && (left.max.compareTo(nodeValue) <= 0) 
	    && (right.min.compareTo(nodeValue) >= 0);
	
	    return new Triplet(isBST, left.min, right.max );
    }

    public static void main(String[] args) {

        TreeCell silly = new TreeCell ("Hello");
        System.out.println(isBST(silly));

	TreeCell t = new TreeCell("Jello",
				  new TreeCell ("Hello"),
				  new TreeCell ("Mello"));

        System.out.println(isBST(t));

	t = new TreeCell("Hello",
			 new TreeCell ("Mello"),
			 new TreeCell ("Jello"));

        System.out.println(isBST(t));
    }
}

class Triplet {
    protected boolean isBST;
    protected Comparable min;
    protected Comparable max;
    public Triplet(boolean b, Comparable mini, Comparable maxi) {
	isBST = b;
        min = mini;
	max = maxi;
    }
    public String toString() {
	return isBST + " " + min + max;
    }
}