class SearchTree <E extends Comparable<E>>{
    private E key;
    private SearchTree<E> left, right;

    public SearchTree(E k){
                key = k;
        }

    public String toString(){
        return ""+key+"("+((left==null) ? "" : left+",")
                         +((right==null) ? "" : right)
                     +")";
    }

    public void insert(E e){
	if (key.compareTo(e) < 0) 
            if (right != null) right.insert(e);
            else right = new SearchTree<E>(e);
        else if (key.compareTo(e) > 0) 
            if (left != null) left.insert(e);
            else left = new SearchTree<E>(e);

        assert isSearchTree();
    }


    public SearchTree<E> search(E e){
        if (key.compareTo(e)<0) return (right == null) ? null : right.search(e); 
        if (key.compareTo(e)>0) return (left == null) ? null : left.search(e); 
        return this;
    }

    public static<E extends Comparable<E>> E min(E e1,E e2){
        return (e1 == null) || ((e2!=null) && e1.compareTo(e2) <= 0) ? e1 : e2;
    }
    public static<E extends Comparable<E>> E max(E e1,E e2){
        return (e1 == null) || ((e2!=null) && e1.compareTo(e2) <= 0) ? e2 : e1; 
    }
    public E max(){
        E temp = (left==null) ? key : max(key,left.max());
        return (right==null) ? temp : max(temp,right.max());
    }
    public E min(){
        E temp = (left==null) ? key : min(key,left.min());
        return (right==null) ? temp : min(temp,right.min());
    }


    public boolean isSearchTree(){ 
        return
            ((left==null) ? true : (key.compareTo(left.max())>=0) && left.isSearchTree())
            &&
            ((right==null) ? true : 
                             (key.compareTo(right.min())<=0) && right.isSearchTree());
    }

    public int height(){
        return 1 + Math.max(left==null ? 0 : left.height(), 
                            right==null ? 0 : right.height());
    }

    public boolean isBalanced(){
        return 
            Math.abs((left==null ? 0 : left.height()) - 
                     (right==null ? 0 : right.height())) <= 1 
            && (left==null ? true : left.isBalanced()) 
            && (right==null ? true : right.isBalanced());
    }

    public static SearchTree<Integer> random(int n){
        if (n<0) return null;
        java.util.Random generator = new java.util.Random();
        SearchTree<Integer> t = new SearchTree<Integer>(generator.nextInt());
        for (int i=1;i<n;i++)
            t.insert(generator.nextInt());
        return t;
    }
}