import java.util.*;
import java.io.*;

public class BinarySearchTree<E> {
	private BinaryNode<E> root;

	/**
	 * Construct an empty binary searchtree
 	 */
	public BinarySearchTree() {
		root = null;
	}

	/**
	 * Return a reference to the root of the tree
 	 */
	public BinaryNode getRoot() {
		return root;
	}
    
	/**
	 * Insert a new item in tree.
	 * @param x the item to insert.
	 */
	 
	 
	public void insert(E x) {
		root = insert((Comparable)x, root);
	}

	protected BinaryNode insert( Comparable x, BinaryNode t ) {
        if(t == null)
            t = new BinaryNode(x);
        else if(x.compareTo(t.element) < 0)
            t.left = insert(x, t.left);
        else
            t.right = insert(x, t.right);
        
        return t;
    }
    
   
    public static void main(String[] args) {
    	BinarySearchTree t = new BinarySearchTree( );
   /*    
		for( int i = 15; i != 0; i--)
 			t.insert( new Integer( i ));
     	t.printTree();
     */	
     	
    }

	/**
	 * Compute height of tree.
	 */
	public int height() {
		return height(root);
	}

	/**
	 * Print tree contents inorder.
	 */
	public void printTree() {
		if (root != null) {
			printTree(root);
		}
	}
   
	/**
 	 * Rebuild tree. The result is a complete tree.
	 */
	public void rebuild() {
		E[] contents = inorderArray();
		root = buildTree(contents, 0, contents.length-1);
 	}

	/* ----------------   Auxiliary private methods -----------------*/

	private int height(BinaryNode n) {
		if (n == null) {
			return -1;
		} else {
			return 1 + Math.max(height(n.left), height(n.right));
		}
	}

   
	private void printTree(BinaryNode n) {
		if (n.left != null) {
			printTree(n.left);
		}
		System.out.println(n.element);
		if (n.right != null) {
			printTree(n.right);
		}
	}
   
      
	/* Construct an array of items in tree in ascending order */
	private E[] inorderArray() {
		LinkedList<E> list = new LinkedList<E>();
		if (root != null) {
			inorderList(root,list);
		}
		return  (E[]) list.toArray((E[]) new Comparable[1]);
	}

	/* Add items from tree rooted at n in inorder to the linked list */
	private void inorderList(BinaryNode<E> n, LinkedList<E> list) {
		if (n.left != null) {
			inorderList(n.left,list);
		}
		list.add(n.element);
		if (n.right != null) {
			inorderList(n.right,list);
		}
	}

	/* Build a complete tree from the elements a[first]..a[last].
	   Elements in a are assumed to be in ascending order.
	  Return root of tree.                               
	 */
	private BinaryNode<E> buildTree(E[] a, int first, int last) {
		if(first > last)
			return null;
			
		int root = first+(last-first)/2;
		
		BinaryNode node = new BinaryNode(a[root]);
		node.left = buildTree(a, first, root-1);
		node.right = buildTree(a, root+1, last);
		
		return node;
	}
   
}