public class BinarySearchTree {
	
	/**
	 *  A node of the binary search
	 */
	private class Node
	{
		private int value = -4;
		// Either - or +
		private String direction = "";
		
		private Node left = null;

  		private Node right = null;
  		
  		public Node(int value, String direction)
  		{
  			this.value = value;
  			this.direction = direction;
  			print();
  		}

		public void add(int value)
		{
			// Print own node before creating or assigning node responsibilities.
			print();
			
			// Remember to assign a direction! + or -
			String directionToAssign = choose("-", "+");
			
			if( directionToAssign.equals("-") )
			{
				if( this.left == null )
				{
					// We dont have a left node
					this.left = new Node(value, directionToAssign);
					
				}
				else
				{
					// We have a left node. Pass him the responsibility!
					this.left.add(value);
				}
			}
			else // "+"
			{
				if( this.right == null )
				{
					// We dont have a right node
					this.right = new Node(value, directionToAssign);
				}
				else
				{
					// We have a left node. Pass him the responsibility!
					this.right.add(value);
				}
			}
		}
		
		public void print()
		{
			if( direction.equals("*") )
			{
				System.out.printf("%d", value);
			}
			else
			{
				System.out.printf(" %s%d", direction, value);
			}
		}
		
		public int getDepth(int depth)
		{
			if( (this.left==null) && (this.right==null) )
			{
				// Last node here!
				return depth;
			}
			else
			{
				if( (this.left!=null) && (this.right==null) )
				{
					//Only left exists
					return this.left.getDepth(depth + 1);
				}
				else if( (this.left==null) && (this.right!=null) )
				{
					//Only right exists
					return this.right.getDepth(depth + 1);
				}
				else
				{
					//Both exist
					return Math.max(this.left.getDepth(depth + 1), this.right.getDepth(depth + 1));
				}
			}
		}
	}
	
	// Store root node, if null, tree is empty
	private Node root = null;
	
	public boolean isTreeEmpty()
	{
		return (root == null);
	}
	
	public static String choose(String string1, String string2) {
		if( Math.random() > 0.5 )
		{
			return string1;
		}
		else
		{
			return string2;
		}
	}

	/** */
	public void add( int value )
	{
		// The add is different if tree is empty
		if( isTreeEmpty() )
		{
			// Use * for root direction.
			root = new Node(value, "*");
		}
		else
		{
			root.add(value);
		}
	}
	
	
	/** Loose its root reference, thus returning to an empty tree */
	public void restart()
	{
		this.root = null;
	}
	
	/** Print the position of the node that is farthest to root */
	public void printLevel()
	{
		int depth = -1;
		if( !isTreeEmpty() )
		{
			depth = root.getDepth(0);
		}
		System.out.printf("%d%n", depth );
	}
	
}