// (unbalanced) binary search trees, 2019 version b.
// to run demo main, must compile with Bst.java and BstDisplay.java

/* Find the following interface in Bst.java:
interface Bst<T extends Comparable<T>>
{
    int size();
    int depth();
    boolean isEmpty();
    Bst<T> insert(T x);
    boolean search(T x);
    Bst<T> delete(T x);
    boolean isSearchTree(T min, T max); // check if tree is a BST
}//interface Bst
*/

class Nil<T extends Comparable<T>> implements Bst<T>
{
    public int size() { return 0; }
    public int depth() { return 0; }
    public boolean isEmpty() { return true; }
    public boolean search(T x) { return false; }
    public Bst<T> insert(T x)
    {
	return new Vertex<T>(x,this,this); // reuse instance of Nil
    }
    // call insert using  tree = tree.insert(x);
    public Bst<T> delete(T x) { return this; }
    public boolean isSearchTree(T min, T max) { return true; }

    public String toString() { return ""; }

    // if item() is in Bst interface:
    //public T item() {throw new RuntimeException("nil has no item"); }
}//Nil

class Vertex<T extends Comparable<T>> implements Bst<T>
{
    protected T item;
    protected Bst<T> left;
    protected Bst<T> right;
    public T item() { return item; }
    public Bst<T> left() { return left; }
    public Bst<T> right() { return right; }
    public Vertex(T i, Bst<T> lf, Bst<T> rt)
    {  item=i;  left=lf;  right=rt;  setheight(); } // constructor
    
    public int size() { return 1+left.size()+right.size(); }
    public int depth()
    {   return height;   // height variable declared below
	//return Math.max(left.depth(),right.depth()) + 1; //recursive solution
    }
    public boolean isEmpty() { return false; }
    public boolean search(T x)
    {
	int c = item.compareTo(x);
	return c==0 || (c>0 && left.search(x)) || (c<0 && right.search(x));
    }
    public Bst<T> insert(T x)
    {
	int c = item.compareTo(x);
	if (c==0) return this; // no duplicates
	if (c>0) left = left.insert(x);
	else if (c<0) right=right.insert(x);
	adjust();
	return this;
    }//insert

    // delete requires two procedures - delete and delmax
    protected Bst<T> delmax(Vertex<T> modnode) // delete largest, change modnode
    {
	if (right.isEmpty()) // this node holds largest value
	    {
		modnode.item = this.item;
		return left; // left subtree may not be empty!
	    }
	else
	    right = ((Vertex<T>)right).delmax(modnode);
	adjust();
	return this;
    }//delmax helper function for delete

    public Bst<T> delete(T x)
    {
	int c = item.compareTo(x); // find it first
	if (c<0) right = right.delete(x);
	else if (c>0) left = left.delete(x);
	else  // found node to delete
	    {
		if (left.isEmpty()) return right;
		else left = ((Vertex<T>)left).delmax(this);
	    }
	adjust();
	return this;
    }//delete

    public boolean isSearchTree(T min, T max)
    {
	return (min==null || min.compareTo(item)<0) &&
	    (max==null || max.compareTo(item)>0) &&
	    left.isSearchTree(min,item) && 
	    right.isSearchTree(item,max);
    } // null here is used to represent +/- infinity

    // inorder traversal
    public String toString()
    { return left.toString()+" "+item+" "+right.toString(); }
	
    
    // for better depth function: O(1):
    protected int height;
    protected int setheight()
    {
	int dl = left.depth(), dr = right.depth();
	height = Math.max(dl,dr)+1;
	return dl-dr; // return height balance
    }

    protected void adjust() // adjust after insert/delete
    {
	setheight();  // what's this for?  redundant?
    }
}//Vertex

public class bst19
{
    public static void main(String[] av) throws Exception
    {
	Bst<Integer> A = new Nil<Integer>(); // start with empty tree
	for(int i=0;i<128;i++)
	    A = A.insert( (int)(Math.random()*256) );

	BstDisplay G = new BstDisplay(1024,768); // for graphical drawing
	G.drawtree(A);
        G.display.drawString("height="+(A.depth()), 30, 60);
        G.display.drawString("size="+(A.size()), 30, 100);

	Thread.sleep(8000); // 8 second delay
	for(int i=0;i<64;i++)
	    A = A.delete((int)(Math.random()*256)); // delete random nodes.
	G.drawtree(A);
        G.display.drawString("height="+(A.depth()), 30, 60);
        G.display.drawString("size="+(A.size()), 30, 100);	
	G.display.drawString("after delete", 30,140);
    }//main
}//bst19