import java.lang.Math;
import java.util.Vector;
/**
   This class implements a binary search tree whose
   nodes hold objects that implement the Comparable
   interface.
*/
class Node<U extends Comparable<U>>
    {
        public U data;
        public Node<U> left, right;
        public Node(U obj){
            data = obj;
            left = right = null;
        }
        /**
           Inserts a new node as a descendant of this node.
           @param newNode the node to insert
        */
        public void insertNode(Node<U> newNode)
        {
            if (newNode.data.compareTo(data) < 0) {
                if (left == null)
                    left = newNode;
                else
                    left.insertNode(newNode);
            } else {
                if (right == null)
                    right = newNode;
                else
                    right.insertNode(newNode);
            }
        }
      /**
         Prints this node and all of its descendants
         in sorted order.
      */
    public void printNodes() {
        if (left != null)
            left.printNodes();
        System.out.println(data);
        if (right != null)
            right.printNodes();
    }
    public boolean search(U key){
        System.out.println("Checking "+data);
        int cval = data.compareTo(key);
        if (cval == 0) {
            return true;
        } else if (cval > 0) {
            if  (left == null)
                return false;
            else
                return left.search(key);
        } else {
            if (right == null)
                return false;
            else
                return right.search(key);
        }
    }

    public int depth(){
        int rdepth =
            (right==null) ? 0 : right.depth();
        int ldepth =
            (left==null) ? 0 : left.depth();

        return 1 + Math.max(rdepth, ldepth);
    }

    public U first(){
        if (left == null)
            return data;
        else
            return left.first();
    }

    public U last(){
        if (right == null)
            return data;
        else
            return right.last();
    }


}


public class BinarySearchTree
    <T extends Comparable<T>> {
    private Node<T> root;
    public BinarySearchTree() {
        root = null;
    }
    /**
       Inserts a new node into the tree.
       @param obj the object to insert
    */
    public void insert(T obj)
    {
        Node<T> newNode = new Node<T>(obj);
        if (root == null)
            root = newNode;
        else
            root.insertNode(newNode);
    }
    /**
       Prints the contents of the tree in sorted order.
    */
    public void print()
    {
        if (root != null)
            root.printNodes();
    }

    static public <U extends Comparable<U>>
        BinarySearchTree<U> fromSorted(Vector<U> items){

        BinarySearchTree<U> tree= new BinarySearchTree<U>();

        tree.root=BinarySearchTree.fromSorted(items,0,items.size()-1);
        return tree;
    }

    static private <U extends Comparable<U>>
        Node<U> fromSorted(Vector<U> items,  int first, int last){
        if (first > last)
            return null;

        int mid = (first + last)/2;

        Node<U> root = new Node<U>(items.elementAt(mid));

        root.left=fromSorted(items,first,mid-1);
        root.right=fromSorted(items,mid+1,last);
        return root;
    }

    public boolean search(T key){
        if (root == null)
            return false;
        else
            return root.search(key);
    }

    public int depth(){
        return (root==null) ? 0 : root.depth();
    }

    public T first(){
        return (root==null) ?  null : root.first();
    }


    public T last(){
        return (root==null) ?  null : root.last();
    }

    public static void main(String[] args)    {
        BinarySearchTree<String> staff
            = new BinarySearchTree<String>();

        staff.insert("Romeo");
        staff.insert("Juliet");
        staff.insert("Tom");
        staff.insert("Dick");
        staff.insert("Harry");

        staff.print();
    }
}