public class BST implements SearchStructure {

    private BinaryNode root;
    private BinaryNode current;
    private int size;

    public BST( ) {
	root = null;
    }

    public void delete(Object o) {}

    public int size() { 
	return size; }

    public boolean search(Object o) { 
	current = mySearch(o,root); // set finger into BST
	// doublechecking: no empty tree, data the same:
	return (current!=null && current.getItem().equals(o));
    }
    
    // search helper
    private BinaryNode mySearch(Object o, BinaryNode r) {
	if (r == null)
	    return null;
	int test = ((Comparable) r.getItem()).compareTo(o);
	if (test > 0) 
	    return mySearch(o, r.getLeft());
	else if (test < 0) 
	    return mySearch(o, r.getRight());
	else
	    return r;
    }
    
    public Comparable findMax() {
	return findMax(root);
    }

    private Comparable findMax(BinaryNode r) {
	if (r==null) return null;
	if (r.getRight()==null) return (Comparable) r.getItem();
	else return findMax(r.getRight());
    }

    public void insert (Object o)  {
	root = insert(o,root);
	size++;
    }

    private BinaryNode insert(Object o, BinaryNode r) {
        if (r == null)
            r = new BinaryNode(o);
	else if (((Comparable) r.getItem()).compareTo(o) > 0) 
	    r.setLeft(insert(o,r.getLeft()));
	else if (((Comparable) r.getItem()).compareTo(o) < 0) 
	    r.setRight(insert(o,r.getRight()));
	return r; // actually, not good (no dups!)
    }

    public boolean isEmpty() {
        return root == null;
    }
    public BinaryNode getRoot() {
        return root;
    }
    public void setRoot(BinaryNode root) {
	this.root=root;
    }
    public int getHeight() {
	return root.getHeight();
    }
    public String toString() {
	return root.toString();
    }
    public String toTree() {
	return root.toTree();
    }


}