/*  SearchTree.java       Authors: Koffman & Wolz
 *  Class for binary search tree that stores Comparable objects.
 */
public class SearchTree  {

  // Insert inner class TreeNode here.
  private class TreeNode {
	  // Data Fields
	  private Comparable info;
	  private TreeNode left;
   	private TreeNode right;

	  // Methods
   	// Constructors
	  public TreeNode() {};

	  public TreeNode(Object obj) {
	  	info = (Comparable) obj;  // cast obj
	   	left = null;
		  right = null;
	  }

   	public boolean insertNode(Object item) {
      if (info.compareTo(item) == 0)
	   		return false;
	   	else if (info.compareTo(item) > 0)
			  // item key < root key - check left subtree
			  if (left == null) {
			    left = new TreeNode(item); // Insert item.
			    return true;
		   	} else  // Insert item in left subtree.
			    return left.insertNode(item);
		  // item key > root key - check right subtree
		  else if (right == null) {
			  right = new TreeNode(item); // Insert item.
			  return true;
		  } else  // Insert itemin right subtree.
			  return right.insertNode(item);
	  }
  } // class TreeNode

	// Data fields for SearchTree
	private TreeNode root;

	//Methods
	/* Inserts item into a binary search tree.
	   precondition : none
	   postcondition: Returns true if the insertion is
	                  performed. Returns false if there
	                  is a node with the same key as item.
	*/
	public boolean insert(Object item) {
		if (isEmpty()) { // empty search tree
		   root = new TreeNode(item); // Insert item in root.
		   return true;
		} else  // Find insertion point and insert item.
		   return root.insertNode(item);
	}


	public boolean isEmpty() {
		return (root == null);
	}

	public boolean search(Object target) {
		return search(root, target);
	}

	private boolean search(TreeNode root, Object target) {
		if (isEmpty())
			return false;           // Tree is empty.
		else if
		(root.info.compareTo(target)
		   == 0)
			return true;          // Target is found.
		else if	(root.info.compareTo(target) > 0)
			// target key < root key - check left subtree
			if (root.left == null)
				return false;  // Left subtree empty.
			else  // Search left.
				return search(root.left, target);
		// target key > root key - check right subtree
		else if (root.right == null)
			return false;     // Right subtree empty.
		else  // Search right.
			return search(root.right, target);
	}

  public String toString() {
		return toString(root);
	}

	private String toString(TreeNode root) {
    if (root == null)
      return "";
		else {
			// Concatenate string formed from left subtree
      //   with current node and with string
      //   formed from right subtree.
			return toString(root.left) +
             root.info + "\n" +
             toString(root.right);
		}
	}

} // class SearchTree