import java.io.PrintStream;
import java.util.Scanner;

public class RandomBinaryTree 
{
	/**
	 * A node of the binary search tree stores a pair (key,value)
	 * and knows its children: the left node and the right node.
	 * This class is also able to do several tree operations, such
	 * as insertion, removal, and searching of nodes.
	 */
	private class Node
	{

		int way [] = new int [10];
		/**
		 * The value to be stored as a String
		 */
		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 = "";


		/**
		 * Constructs a Node with the given key and value
		 * No children are created
		 * 
		 * @param key The key to be stored
		 * @param value The value to be stored
		 */
		public Node(int value, String sign)
		{

			this.value = value;
			this.direction = sign;
			print();

		}

		public void insert(int value)
		{
			// For example if this node's key is "body" and value to be
			// inserted in the tree is "board" the comparison will return
			// "board".compareTo("body") == -3, so it must be inserted in
			// the left subtree

			print();
			int random = (int)(Math.random()*10);

			if (random < 5)
			{
				// Check if we have a left subtree
				if ( this.left == null )
				{
					// We do not have a left subtree, create it
					String direction = "-";
					this.left = new Node(value, direction);


				}
				else
				{
					// We have a left subtree, insert the (key,value) there
					this.left.insert(value);
				}
			}
			else 
			{
				// The key to be inserted must go in the right subtree
				// Check if we alread have a right subtree
				if ( this.right == null )
				{
					// We do not have a right subtree, create the node there
					String direction = "+";
					this.right = new Node( value, direction);

				}
				else
				{
					// We already have a right subtree, insert the node there
					this.right.insert( value);
				}
			}
		}

		public void print()
		{
			if (this.direction.equals(""))
			{
				System.out.printf("%d", value);
			}
			else
			{
				System.out.printf(" %s%d", direction, value);

			}

		}

		/**
		 * limpia los nodos hijos de la raiz, dejandolos en null
		 */
		public void clean ()
		{
			this.left = null;
			this.right = null;
		}


		/**
		 * metodo recursivo que cuenta cuantos niveles tiene el arbol, 
		 * evaluando de izquierda a derecha 
		 * @return el numero de niveles quye tiene el arbol
		 */
		public int level()
		{
			// si la raiz no tiene hijos, retorna 0
			if (this.left == null && this.right == null)
			{
				return 0;
			}
			else
			{
				int leftLevel = 0; 
				int rightLevel = 0; 

				if (this.left != null)
				{
					leftLevel = this.left.level();

				}

				if (this.right != null)
				{
					rightLevel = this.right.level();
				}

				return Math.max(leftLevel, rightLevel) + 1 ;

			}

		}


	} // class Node

	/**
	 * A tree simply has a reference to the root node.
	 * If this reference is null, the tree is empty
	 */
	private Node root = null;


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

	public void insert(int value)
	{

		// The insertion depends on if the tree is empty
		if ( this.isEmpty() )
		{
			// The tree is empty, make the new pair the root
			this.root = new Node(value, "");

		}
		else
		{
			// The tree has elements, ask the root to insert
			// the pair (key,value) in its place
			this.root.insert(value);
		}

	}


	/**
	 * Limpia la raiz del arbol
	 */
	public void clean ()
	{
		this.root.clean();
		this.root = null;


	}

	/**
	 * determina la cantidad de niveles o profundidad del arbol 
	 * @return
	 */
	public int level ()
	{
		return this.root.level();
	}




}