public class DisorderBinaryTree
{	
	/**
	 * A node of a disorder binary tree
	 * 
	 */
	private class Node
	{		
		/**
		 * The value of the number
		 */
		private int value = 0;

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

		/**
		 * Reference to the right subtree
		 */
		private Node right = null;

		/**
		 * The String that represents if the value is at right or left
		 */
		private String representationSymbol = "";
		
		private int totalLeaf = 0;
		/**
		 * Constructs a Node with the given value
		 * No children are created
		 * 
		 * @param value The value to be stored
		 */
		public Node(int value)
		{
			this.value = value;
		}

		/**
		 * Tries to insert the given value as a 
		 * child
		 * @param value The value to be stored
		 */
		public void insert(int value)
		{
			// Gets the random position, true to the store at the right
			// false to store at the left
			boolean position = getRandomPosition();
			// If it is true, it means thats goes to the right
			
			// Means that you have to insert it on the right
			if (position)
			{
				// Check if we have a left subtree
				if ( this.right == null )
				{
					// We do not have a right subtree, create it
					this.right = new Node(value);
					this.right.representationSymbol = "+";
					System.out.printf(" %s%d ", this.right.representationSymbol , this.right.value);
				}
				else
				{
					// We have a right subtree, insert the (key,value) there
					this.right.insert(value);
				}
			}
			// Insert it on the left
			else
			{
				// Check if we have a left subtree
				if ( this.left == null )
				{
					// We do not have a left subtree, create it
					this.left = new Node(value);
					this.left.representationSymbol = "-";
					System.out.printf( "%s%d ", this.left.representationSymbol, this.left.value);
				}
				else
				{						
					// We have a left subtree, insert the (key,value) there
					this.left.insert(value);
				}
			}
		}	

		/**
		 * Generates a random position, in order to give a 
		 * random position to the element to insert 
		 * @return
		 */
		public boolean getRandomPosition() 
		{
			return Math.random() < 0.5;

		}

		public int checkLeaf()
		{
			if (this.right != null)
			{
				++this.totalLeaf;
				checkLeaf();
			}
			else
			{
				if (this.left != null)
				{
					++this.totalLeaf;
					checkLeaf();
				}
			}
			return this.totalLeaf;
		}
	}//class node

	/**
	 * A tree simply has a reference to the root node.
	 */
	private Node root = null;
	
	private int actual = 0;
	/**
	 * The number of elements stored in the tree
	 */
	private long count = 0;

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

	/**
	 * Return the count of elements currently stored in the tree
	 * @return The count of elements
	 */
	public long getCount()
	{
		return this.count;
	}

	/**
	 * Reset the collections of number
	 */
	public void resetTree()
	{
		this.root = null;
	}
	/**
	 * Insert the given number in the tree
	 * @param value The value to be stored
	 */
	public void insert(int value)
	{

		// The insertion depends on if the tree is empty
		if ( this.isEmpty() )
		{
			// The tree is empty, make the node
			this.root = new Node(value);
			this.root.representationSymbol = "";
		}
		else
		{
			// If this is the first time that the method is called
			if (this.actual == 1 ) 
			{
				// Print the root
				System.out.printf("%d", this.root.value); 
			}
			// The tree has elements, ask the root to insert
			// the value
			this.root.insert(value);
		}

		// We have one more element stored in the tree
		++this.count;
		++this.actual;
	}


	public int leafLevel()
	{

		if (this.root == null)
			return -1;
		if (this.root.left == null && this.root.right == null)
			return 0;
		//return treeHeight();	   
		return root.checkLeaf();
	}   


	public void printRoot()
	{
		System.out.printf("%d ", this.root.value); 
	}

}