import java.io.PrintStream;

/**
 * Implements a map that associates key and values
 * using a binary search tree
 */
public class BinarySearchTree
{
	/**
	 * 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
	{
		/**
		 * The key to be stored as a String
		 */
		private String key = null;
		
		/**
		 * The value to be stored as a String
		 */
		private String value = null;
		
		/**
		 * Reference to the left subtree, null if none
		 */
		private Node left = null;
		
		/**
		 * Reference to the right subtree, null if none
		 */
		private Node right = null;
		
		/**
		 * 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(String key, String value)
		{
			this.key = key;
			this.value = value;
		}
		
		/**
		 * Tries to insert the given key value as a child
		 * of this node, otherwise, it will be inserted as a child
		 * of the corresponding subtree (left or right)
		 * 
		 * @param key The key to be stored
		 * @param value The value to be stored
		 */
		public void insert(String key, String 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
			if ( key.compareTo(this.key) < 0 )
			{
				// Check if we have a left subtree
				if ( this.left == null )
				{
					// We do not have a left subtree, create it
					this.left = new Node(key, value);
				}
				else
				{
					// We have a left subtree, insert the (key,value) there
					this.left.insert(key, value);
				}
			}
			else // ( key.compareTo(this.key) > 0 )
			{
				// 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
					this.right = new Node(key, value);
				}
				else
				{
					// We already have a right subtree, insert the node there
					this.right.insert(key, value);
				}
			}
			// else: notice we insert repeated keys in the tree, so it can
			// have multiple values for a same key. If we forbid this
			// behavior, we will have a set (in mathematical sense).
		}

		/**
		 * Print this tree in in-order, which gives alphabetical order
		 * @param out
		 */
		public void print(PrintStream out)
		{
			// First, print the entire left subtree recursively
			// because all its keys are less than mine
			if ( this.left != null ) { this.left.print(out); }
			
			// Second, print myself because I am the next 
			out.printf("%s\t%s%n", this.key, this.value);
			
			// Third, print the entire right subtree recursively
			// because all its keys are greater than mine
			if ( this.right != null ) { this.right.print(out); }
		}
		
		/**
		 * Finds the value for the given key. This method
		 * will do log_2(n) comparisons if the tree is balanced
		 * 
		 * @param key The key to be searched
		 * @return The corresponding value for the key, null if
		 * the key is not found in the tree
		 */
		public String findValue(String key)
		{
			// Compare the searched key with my key. E.g: if searching
			// for "board" and I have "body", it will produce:
			// "board".compareTo("body") == -3
			int comparison = key.compareTo(this.key);
			
			// If both keys are identical
			if ( comparison == 0 )
			{
				// I have the value for that key, return it
				return this.value;
			}
			else if ( comparison < 0 )
			{
				// The searched key must be in the left subtree
				if ( this.left == null )
				{
					// But I do not have a left subtree, stop here
					return null;
				}
				else
				{
					// I have a left subtree, search there
					return this.left.findValue(key);
				}
			}
			else
			{
				// The searched key must be in the right subtree
				if ( this.right == null )
				{
					// But I do not have a right subtree, stop here
					return null;
				}
				else
				{
					// I have a right subtree, search there
					return this.right.findValue(key);
				}
			}
		} // findValue()
	} // 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;
	
	/**
	 * 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;
	}

	/**
	 * Insert the given pair (key,value) in the tree
	 * @param key The key to be stored
	 * @param value The value to be stored
	 */
	public void insert(String key, String 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(key, value);
		}
		else
		{
			// The tree has elements, ask the root to insert
			// the pair (key,value) in its place
			this.root.insert(key, value);
		}
		
		// We have one more element stored in the tree
		++this.count;
	}
	
	/**
	 * Prints this tree to the given output in alphabetical order
	 * @param out The file were the tree will be printed
	 */
	public void print(PrintStream out)
	{
		// We can only print a tree if it has values
		if ( ! this.isEmpty() )
		{
			// Print the nodes recursively
			this.root.print(out);
		}
	}
	
	/**
	 * Finds the value for the given key. This method
	 * will do log_2(n) comparisons if the tree is balanced
	 * 
	 * @param key The key to be searched
	 * @return The corresponding value for the key, null if
	 * the key is not found in the tree
	 */
	public String findValue(String key)
	{
		// The search depends on if the tree is empty
		if ( this.isEmpty() )
		{
			// The tree is empty, we do not have a value for the key
			return null;
		}
		else
		{
			// We have elements in the tree, search for the value
			// recursively
			return this.root.findValue(key);
		}
	}
}