import java.io.PrintStream;
import java.util.Random;
/**
 * @author b72905@ecci.ucr.ac.cr
 *
 */
public class Tree 
{
	Random random = new Random();
	/**
	 *
	 */
	private class Node
	{
		/**
		 * The value to be stored as an integer
		 */
		private int value = 0;

		/**
		 * Reference to the left subtree, null if none
		 */
		private Node left = null;

		/**
		 * Reference to the right subtree, null if none
		 */
		private Node right = null;
			
		private String direction = null;
		
    	int remoteness = 0;
 
		/**
		 *
		 */
		public Node(int value, String dir)
		{
			
			this.value = value;
			this.direction = dir;
			this.printPath();
		}

		/**
		 * 
		 */
		public void insert (int value)
		{
			this.printPath();
			
			int direction = rand();
			
			if ( direction == 1)
			{
				if (this.right == null)
				{
					this.right = new Node(value, "+");
				}
				else
				{
					this.right.insert(value);
				}
			}
			else if (direction == 2)
			{
				if (this.left == null)
				{
					this.left = new Node(value, "-");
				}
				else
				{
					this.left.insert(value);
				}
			}
			

		}
		
	    
	    public int getRemoteness( )
	    {	    

	    	
    		if (this.left == null && this.right == null)
    		{
    			return 0;
    		}
    		else
    		{
    	       	int leftRemoteness = 0;
    	    	int rightRemoteness = 0;
    			
    			if (this.left != null)
    			{
    				leftRemoteness = left.getRemoteness();
    			}
    			
    			if (this.right != null)
    			{
    				rightRemoteness = right.getRemoteness();
    			}
    			
    			return Math.max(leftRemoteness, rightRemoteness) + 1;
    		}

	    }
	    
	    public void printPath()
	    {
	 	   if (this.direction.equals("!"))
	 	   {
	 		   System.out.printf("%d ", value);
	 	   }
	 	   else
	 	   {
	 		   System.out.printf("%s%d ",direction, value);
	 	   }
	    }
	    
	} // Class node
	
	public void printResult()
	{
    	System.out.println("The farthest leaf is in the level: " + root.remoteness);
	}
	
	private Node root = null;
	
	public void insert(int value)
	{
		if (this.isEmpty() )
		{
			this.root = new Node(value, "!");
		}
		else
		{
			this.root.insert(value);
		}
		

	}
	
	public void reset()
	{
		this.root.left = null;
		this.root.right = null;
		this.root = null;
		
		System.out.println("Resetted!");
	}
	
	public void printFarthest()
	{
		if (isEmpty())
		{
			System.out.println("The farthest leaf is in the level: " + -1);
			return;
		}
		else
		{
			root.remoteness = root.getRemoteness();
		}	
		
    	printResult();
	}
	
	public boolean isEmpty()
	{
		return root == null;
	}
	
	public int rand()
	{
		return random.nextInt(2) + 1;
	}
	
   
 

}