//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//Binary Search Tree
//Description: A simple Binary Search Tree class that supports insertion and
//  inorder, preorder, and postorder traversals.Based on the Binary Tree class
//  on page 640 of "Introduction to Java Programming" by Y.D. Liang.
//CS 284
//Programmed by Jonathan Voris
//3/29/06
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
import java.util.ArrayList;

public class BinaryTree
{
	private TreeNode root;

	public BinaryTree()
	{
	}

	//This second constructor takes a list of objects and inserts them in
	//order for easier testing.
	public BinaryTree(Object[] objects)
	{
		for (int i=0; i < objects.length; i++)
		{
			insert(objects[i]);
		}
	}

	public boolean insert(Object obj)
	{
		if (root == null)
		{//Create a new root.
			TreeNode tNode = new TreeNode();
			tNode.setData(obj);
			root = tNode;
		}
		else
		{//Locate the parent node.
			TreeNode parent = null;
			TreeNode current = root;
			while (current != null)
			{
				if (((Comparable)obj).compareTo(current.getData()) < 0)
				{//object to insert is less than the current object - move
				 //down its left side.
					parent = current;
					current = current.getLeft();
				}
				else if (((Comparable)obj).compareTo(current.getData()) > 0)
				{//object to insert is greater than the current object - move
				 //down its right side.
					parent = current;
					current = current.getRight();
				}
				else
				{//object to insert is equal to the current object -
				 //don't insert duplicate and return false.
					return false;
				}
			}

			TreeNode tNode = new TreeNode();
			tNode.setData(obj);
			//Create a new node for the object and attach it to the parent node.
			if (((Comparable)obj).compareTo(parent.getData()) < 0)
			{
				parent.setLeft(tNode);
			}
			else
			{
				parent.setRight(tNode);
			}
		}
		//Element inserted correctly
		return true;
	}

	//The public traversal functions start their respective private traversal
	//functions by calling them on the tree's root and passing them an empty
	//list to store the traversal path in.
	public ArrayList inorder()
	{
		ArrayList nodeList = new ArrayList();
		inorder(root, nodeList);
		return nodeList;
	}

	public ArrayList preorder()
	{
		ArrayList nodeList = new ArrayList();
		preorder(root, nodeList);
		return nodeList;
	}

	public ArrayList postorder()
	{
		ArrayList nodeList = new ArrayList();
		postorder(root, nodeList);
		return nodeList;
	}

	//The private traversal functions recursively traverse the tree's
	//left subtree, then its right subtree. The current node is added to
	//the traversal list in the correct position for the type of traversal
	//being performed.
	private void inorder(TreeNode root, ArrayList nodeList)
	{
		if (root == null)
		{
			return;
		}

		inorder(root.getLeft(), nodeList);
		nodeList.add(root.getData());
		inorder(root.getRight(), nodeList);
	}

	private void preorder(TreeNode root, ArrayList nodeList)
	{
		if (root == null)
		{
			return;
		}

		nodeList.add(root.getData());
		preorder(root.getLeft(), nodeList);
		preorder(root.getRight(), nodeList);
	}

	private void postorder(TreeNode root, ArrayList nodeList)
	{
		if (root == null)
		{
			return;
		}

		postorder(root.getLeft(), nodeList);
		postorder(root.getRight(), nodeList);
		nodeList.add(root.getData());
	}

	//Find returns the node containing the key target if it is in the
	//tree and null otherwise.
	public TreeNode find(Object target)
	{
		if (root == null)
		{//If the root is null, the tree is empty, so the target
		 //cannot possibly be in it - return null.
			return null;
		}
		else
		{
			TreeNode parent = null;
			TreeNode current = root;
			while (current != null)
			{
				if (((Comparable)target).compareTo(current.getData()) < 0)
				{//Target is less than the current object - move
				 //down its left side.
					parent = current;
					current = current.getLeft();
				}
				else if (((Comparable)target).compareTo(current.getData()) > 0)
				{//Target is greater than the current object - move
				 //down its right side.
					parent = current;
					current = current.getRight();
				}
				else
				{//Target must be equal to the current object -
				 //return the current Tree Node!
					return current;
				}
			}
		}
		//If we've gotten this far, we have reached the bottom of the
		//tree without finding the target. This means it is not present
		//in the tree, so null should be returned.
		return null;
	}

	//Find returns the true if a node with the key target is in the
	//tree and false otherwise.
	public boolean contains(Object target)
	{
		//Instead of rewritting the traversal code used in insert and
		// find, we can see if our tree contains the desired target
		//by calling contains and checking its result.
		if (find(target) == null)
		{
			return false;
		}
		else
		{
			return true;
		}
	}

}