/* Binary trees and search trees  - Algebraic style */


interface Tree<Ty extends Comparable<Ty>>
{
    public int size();
    public vertex<Ty> find(Ty x);
    public vertex<Ty> bsearch(Ty x);
    public int depth();
    public Tree<Ty> insert(Ty x);
}

// class for empty tree - not using "null"
class nil<Ty extends Comparable<Ty>> implements Tree<Ty>
{
    public int size() { return 0; }
    public vertex<Ty> find(Ty x) { return null; }
    public vertex<Ty> bsearch(Ty x) {return null;}
    public int depth() {return 0;}
    public Tree<Ty> insert(Ty x) { return new vertex<Ty>(x); }
}

// class for a non-nil vertex or node, with a head, left and right:
class vertex<Ty extends Comparable<Ty>> implements Tree<Ty>
{
    Ty head;
    Tree<Ty> left;
    Tree<Ty> right;

    // constructors
    public vertex(Ty h, Tree<Ty> l, Tree<Ty> r) {head=h; left=l; right=r;}
    public vertex(Ty h) {head=h; left = new nil<Ty>(); right = new nil<Ty>();}

    // function to compute total number of vertexs:

    public int size()
    {
	return left.size() + right.size() + 1;
    }

    // function to determine if an element is in the tree, NOT assuming
    // that the tree is a binary-search tree.  It returns a pointer to
    // the vertex containing the element, or null if non exists

    public vertex<Ty> find(Ty x)
    {
	if (head.equals(x)) return this; // this is the vertex with x
	vertex<Ty> l = left.find(x);
	if (l!=null) return l; 
	else return right.find(x);
    }
    

    // function to find an element, assuming a BST structure, where
    // all elements on the left subtree are <= to the root element.

    public vertex<Ty> bsearch(Ty x)
    {
	if (head.equals(x)) return this;
	if (x.compareTo(head)<0) // go left
		 return left.bsearch(x);
	else // go right
	         return right.bsearch(x); 
    }

    // function to insert a new element into the tree
    public Tree<Ty> insert(Ty x)
    {
	if (x.compareTo(head)<=0) // go left
	    left = left.insert(x);
	else right = right.insert(x);
	return this; // root vertex has not changed.
    }//insert
 

    // function to find the maximum depth of the tree.  The depth of a 
    // tree is one plus the depth of the deeper subtree.  That's recursion
    // for you!
    public int depth()
    {
	int dl = left.depth();
	int dr = right.depth();
	if (dl > dr) return dl+1;  else return dr+1;
    }
}// vertex