/**
 * A Binary Search Tree of Objects.
 * <p>
 * This class creates a tree of objects where, for each node, objects
 * with a smaller value can be found in the left subtree and objects with
 * a greater value can be found in the right subtree.  Duplicate objects
 * (meaning compareTo between the two would ==0) are not allowed.
 *
 * @author Blanca Polo
 * @author Zach Tomaszewski
 * @version 18 Nov 2003
 */
public interface BST{


  /**
   * Determines whether or not the tree is empty.
   * 
   * @return   true if there are no elements in the tree (size() == 0),
   *    otherwise returns false.
   */
  public boolean isEmpty();
  

  /**
   * Returns the size of the BST.
   *
   * @return the number of elements in the BST
   */
  public int size();
  

  /**
   * Inserts (adds) an element into this BST.
   * Follows the BST rules:
   * <ul>
   * <li>no duplicate elements are accepted
   * <li>for every node N, 
   * the left child will have a key smaller than N's key and
   * the right child will have a key greater than N's key
   * </ul>
   *
   * @param item   the Comparable object to insert into this BST
   * @throws BSTException  if the object is a duplicate (matches an element
   *                       already in the tree) or cannot be inserted
   */
  public void insert(Comparable item) throws BSTException;


  /**
   * Retrieve (gets) an element from this BST.
   * This is primarily so you can use a simple key object to retrieve 
   * a complete data object stored in the tree.
   *
   * @param key  an item to find/match in the tree
   * @return   the Comparable object that matches (compareTo == 0)
   *           the given key
   * @throws BSTException  if there is no matching item in the tree
   */
  public Comparable retrieve (Comparable key) throws BSTException;


  /**
  * Removes an item from within this BST.
  * Updates the tree to maintain its sorted order.
  * <p>
  * Returns the item actually found in the tree, since some Comparables 
  * only compareTo on a key 
  * (that is, <code>nodeItem.compareTo(item) == 0</code>
  * may not be the same as <code>nodeItem.equals(item)</code>)
  *
  * @return the Comparable object actually removed from the tree
  * @throws BSTException  if the object cannot be removed 
  *                       (such as when it cannot be found in the tree)
  */
  public Comparable remove (Comparable item) throws BSTException;


  /**
   * Removes all elements from this BST.
   * <code>size()</code> is then 0.
   */
  public void removeAll ();
  

  /**
   * Returns a String of all the elements in this BST.
   * <p>
   * By default, the tree it traversed such that the elements are listed 
   * from smallest to greatest in the output.  
   * However, this (inorder) traversal behavior may
   * be overridden through the use of other methods 
   * in the implementing class that set a different traversal order.
   */
  public String toString();

} //interface ends