// The test harness will belong to the following package; the BST
// implementation will belong to it as well.  In addition, the BST
// implementation will specify package access for the inner node class
// and all data members in order that the test harness may have access
// to them.
//
package MinorP2.DS;

public class BST<T extends Comparable<? super T>> {
	
    class BinaryNode {
       // Initialize a childless binary node.
       public BinaryNode( T elem ) { . . . }
       // Initialize a binary node with children.
       public BinaryNode( T elem, BinaryNode lt, BinaryNode rt ) { . . . }

       T          element;  // The data in the node
       BinaryNode left;     // Pointer to the left child
       BinaryNode right;    // Pointer to the right child
    }

    BinaryNode root;        // pointer to root node, if present.

    // Initialize empty BST; an empty BST contains no nodes.
    public BST( ) { . . . }
	// Return true iff BST contains no nodes.
    public boolean isEmpty( ) { . . . }
	// Return pointer to matching data element, or null if no matching
    // element exists in the BST.  "Matching" should be tested using the
    // data object's compareTo() method.
    public T find( T x ) { . . . }
    // Insert element x into BST, unless it is already stored.  Return true
    // if insertion is performed and false otherwise.
    public boolean insert( T x ) { . . . }
	// Delete element matching x from the BST, if present.  Return true if
    // matching element is removed from the tree and false otherwise.
    public boolean remove( T x ) { . . . }
	// Return the tree to an empty state.
    public void clear( ) { . . . }
    // Return true iff Other is a BST that has the same physical structure
	// and stores equal data values in corresponding nodes.  "Equal" should
	// be tested using the data object's equals() method.
    public boolean equals(Object other);
}