public class StrBSTree {
	private class Node
	{
		private String data;
		private Node leftChild;
		private Node rightChild;
		public Node(String aData)
		{
			data = aData;
			leftChild = null;
			rightChild = null;
		}
	}
	private Node root;
	public StrBSTree()
	{
		root = null;
	}
	public void insert(String aData)
	{
		if (root == null)
		{
			root = new Node(aData);
		}
		else
		{
			insert(root, aData);
		}
	}
	private Node insert(Node aNode, String aData)//Recursive Method
	{
		if (aNode == null)//Found a leaf
		{
			aNode = new Node(aData);
		}
		else if (aData.compareTo(aNode.data) < 0)//Go left
		{
			aNode.leftChild = insert(aNode.leftChild, aData);
		}
		else if (aData.compareTo(aNode.data) >= 0)//Go right
		{
			aNode.rightChild = insert(aNode.rightChild, aData);
		}
		return aNode;
	}
	public void remove(String aData)
	{
		root = remove(root, aData);
	}
	private Node remove(Node aNode, String aData)
	{
		//Find the node
		if (aNode == null)
		{
			return null;
		}
		if (aData.compareTo(aNode.data) < 0)//Left
		{
			aNode.leftChild = remove(aNode.leftChild, aData);
		}
		else if (aData.compareTo(aNode.data) > 0)//Right
		{
			aNode.rightChild = remove(aNode.rightChild, aData);
		}
		else//Found it
		{
			if (aNode.rightChild == null)//None or only left child
			{
				return aNode.leftChild;
			}
			if (aNode.leftChild == null)//Right child only
			{
				return aNode.rightChild;
			}
			//Two children
			Node min = findMinInTree(aNode.rightChild);
			aNode.data = min.data;
			aNode.rightChild = remove(aNode.rightChild, min.data);
		}
		return aNode;
	}
	private Node findMinInTree(Node aNode)
	{
		if (aNode == null)
		{
			return null;
		}
		if (aNode.leftChild == null)
		{
			return aNode;
		}
		else
		{
			return findMinInTree(aNode.leftChild);
		}
	}
	public void printPreOrder()
	{
		printPreOrder(root);
	}
	private void printPreOrder(Node aNode)
	{
		if (aNode == null)
		{
			return;
		}
		System.out.println(aNode.data);//Process
		if (aNode.leftChild != null)//Left
		{
			printPreOrder(aNode.leftChild);
		}
		if (aNode.rightChild != null)//Right
		{
			printPreOrder(aNode.rightChild);
		}
		return;
	}
	public int getHeight()
	{
		return getHeight(root, 0);
	}
	private int getHeight(Node aNode, int count)
	{
		if (aNode == null)
		{
			return count;
		}
		count++;
		return Math.max(getHeight(aNode.leftChild, count), getHeight(aNode.rightChild, count));
	}
}