import java.util.Iterator;
/**
 * Interface for the Search Tree ADT.
 * @author Jadrian Miles
 */
public interface SearchTree<T extends Comparable<? super T>>
        extends Iterable<T> {
    /** Checks whether the given item is in the tree.
     * @param item The item to look for.
     * @return true if that item is in the tree.
     */
    public boolean contains(T item);
    
    /** Adds the given item to the tree.
     * @param item The item to add.
     */
    public void add(T item);
    
    /** Removes the given item from the tree.
     * @param item The item to add.
     */
    public void remove(T item);
    
    /** Returns the height of the tree. */
    public int height();
    
    /** Returns the number of items in the tree. */
    public int size();
    
    /** Removes all items from the tree. */
    public void clear();
    
    /** Returns whether the tree is empty. */
    public boolean isEmpty();
    
    /** Returns a list of all the items in this search tree in order. */
    public List<T> inOrderTraversal();
    
    /** Returns an iterator over the in-order traversal of the tree. */
    public Iterator<T> iterator();
    
    /** Returns a List of all the items in the tree, ordered as in a pre-order
     * traversal.
     */
    public List<T> preOrderTraversal();
    
    /** Returns a List of all the items in the tree, ordered as in a prost-order
     * traversal.
     */
    public List<T> postOrderTraversal();
}