/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Dominik Gruntz
*/
class BinarySearchTree {
	private Node root;
	
	/**
	* Searches an item in the tree.
	* @param key the key to search for.
	* @return the matching item or null if not found.
	*/
	public Object search (Comparable key){
		return search(root, key);
	}
		
	private Object search (Node p, Comparable key){
		if(p == null)
			return null;
		else {
			int c = key.compareTo(p.key);
			if (c > 0) return search(p.right, key);
			else if (c < 0) return search(p.left, key);
			else return p.element;
		}
	}
	
	/**
	* Computes the number of nodes in the tree
	* @return size of the tree.
	*/
	public int size(){
		return size(root);
	}
	
	private int size(Node p){
		if(p==null)return 0;
		else return 1 + size(p.left) + size(p.right);
	}

	/**
	* Test if the tree is logically empty.
	* @return true if empty, false otherwise.
	*/
	public boolean isEmpty( ) {
		return root == null;
	}

	/**
	* Insert a value into the tree; if an element is already stored under
	* the given key the element is replaced by the new one.
	* @param key key with which the specified element is to be associated.
	* @param element element to be inserted into the tree.
	*/
	public void insert (Comparable key, Object element){
		root = insert(root, key, element);
	}

	/**
	* Internal method to insert into a subtree.
	* @param p the node that roots the tree.
	* @param key the key of the element to insert.
	* @param element the element to insert.
	* @return the new root.
	*/
	private Node insert(Node p, Comparable key, Object element){
		if (p==null) 
			return new Node(key, element);
		else {
			int c = key.compareTo(p.key);
			if (c < 0)
				p.left = insert(p.left, key, element);				
			else if(c > 0)
				p.right = insert(p.right, key, element);
			else
				p.element = element;
			return p;
		}
	}
	
	public String toString(){
		return root == null ? "[]" : root.toString();
	}

				
	/**
	* Remove from the tree. Nothing is done if x is not found.
	* @param x the item to remove.
	*/
	public void remove (Comparable key){}	
}

class Node {
	Comparable key;
	Object element;
	Node left, right;
	
	Node(Comparable key){this(key, null);}
	Node(Comparable key, Object element){
		this.key = key; this.element = element;
	}
	Node(Comparable key, Object element, Node left, Node right){
		this(key, element); this.left = left; this.right = right;
	}
	
	public String toString(){
		if(left == null && right == null)
			return "[" + key + "]";
		else
			return "[" + key + (left !=null?left.toString():"[]") 
				   		 + (right!=null?right.toString():"[]") + "]";
	}		

}