//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//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;
	}

//Stay tuned! Traversals coming next week!

}