public class BinaryTree
{
	private BinaryTreeNode root = null;
	
	public BinaryTree()
	{
	}
	
	public boolean isEmpty()
	{
		if (root == null)
			return true;
		else
			return false;
		
		//return root == null;
	}

	public void print()
	{
		if (!isEmpty())
			printSubtree(root);
	}
	
	private void printSubtree(BinaryTreeNode current)
	{
		if (current == null)
			return;
		
		if (current.left != null)
			printSubtree(current.left);
				
		System.out.println(current.num + " ");
		
		if (current.right != null)
			printSubtree(current.right);			
	}
	
	public BinaryTreeNode find(int num)
	{
		if (!isEmpty())
			return findSubtree(num, root);
		return null;
	}
	
	public BinaryTreeNode findSubtree(int num, BinaryTreeNode current)
	{
		//if you reach null, then num is not in the tree
		if (current == null)
			return null;
		
		//if you find the num, then you can return its node
		if (current.num == num)
			return current;
	
		//if the number we're looking for is less than the current num, then go left
		if (num < current.num)
			return findSubtree(num, current.left);
		
		//if the number we're looking for is less than the current num, then go right
		if (num > current.num)
			return findSubtree(num, current.right);
		
		return null;
	}
	
	public void insert(int num)
	{
		//check for empty tree first
		//if tree is empty, then you MUST set root
		if (isEmpty())
		{
			root = new BinaryTreeNode();
			root.num = num;
		}
		else
		{
			//insert into the subtree starting at the root
			insertInSubtree(num, root);
		}
	}
	
	public void insertInSubtree(int num, BinaryTreeNode current)
	{
		//check for null
		if (current == null)
			return;
		
		//if our current num is the same, then leave because you do NOT want to insert
		if (current.num == num)
			return;
		
		//if the num we're inserting is less than the current num, then we go left
		if (num < current.num)
		{
			//if the node to the left is null, then we are at the leaves and we insert
			if (current.left == null)
			{
				BinaryTreeNode newNode = new BinaryTreeNode();
				newNode.num = num;
				current.left = newNode;
				return;
			}
			//go left if we're not at the leaves yet
			insertInSubtree(num, current.left);
		}
		
		//if the num we're inserting is greater than the current num, then we go left
		if (num > current.num)
		{
			//if the node to the right is null, then we are at the leaves and we insert
			if (current.right == null)
			{
				BinaryTreeNode newNode = new BinaryTreeNode();
				newNode.num = num;
				current.right = newNode;				
				return;
			}
			//go right if we're not at the leaves yet
			insertInSubtree(num, current.right);
		}	
	}
	
	public BinaryTreeNode delete(int num)
	{
		if (!isEmpty())
			return deleteInSubtree(num, root);
		return null;
	}
	
	public BinaryTreeNode deleteInSubtree(int num, BinaryTreeNode current)
	{
		if (current == null)
			return null;
		//go down left if num is less than current num
		if (num < current.num)
			current.left = deleteInSubtree(num, current.left);
		//go down right if num is greater than current num
		else if (num > current.num)
			current.right = deleteInSubtree(num, current.right);
		
		//we finally hit the node we're looking for, but
		//if neither left nor right are null, then we must delete
		//the node from somewhere in the middle of the tree
		else if (current.left != null && current.right != null)
		{
			//check to see if we're removing the root
			if (current == root)
			{
				//find the minimum value in current's right subtree
				BinaryTreeNode minNode = locateMinValue(root.right);
				root.num = minNode.num;
				root.right = deleteInSubtree(minNode.num, root.right);	
			}
			else
			{
				//find the minimum value in current's right subtree
				BinaryTreeNode minNode = locateMinValue(current.right);
				current.num = minNode.num;
				current.right = deleteInSubtree(minNode.num, current.right);
			}
		}
		else
		{
			//check to see if we're removing the root
			if (current == root)
			{
				if (root.left != null)
					root = root.left;
				else
					root = root.right;
			}
			else
			{
				if (current.left != null)
					current = current.left;
				else
					current = current.right;	
			}
		}
		
		return current;
	}
	
	private BinaryTreeNode locateMinValue(BinaryTreeNode current)
	{
		if (current == null)
			return null;
		if (current.left == null) 
			return current;
		return locateMinValue(current.left);
	}
}