// The test harness will belong to the package indicated below; 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 specified data members in order that the test harness may have
// access to them.
//
package Minor.P2.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 BST to an empty state; 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.
    // Pre:
    //       The type T implements the interface Comparable;
    //       x is a reference to a valid object of type T, or is null
    public T find( T x ) { . . . }

    // Insert element x into BST, unless it is already stored.  Return true
    // if insertion is performed and false otherwise.
    // Pre:
    //       The type T implements the interface Comparable;
    //       x is a reference to a valid object of type T, or is null
    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.
    // Pre:
    //       The type T implements the interface Comparable;
    //       x is a reference to a valid object of type T, or is null
    public boolean remove( T x ) { . . . }

	 // Delete the subtree, if any, whose root contains an element matching x.
    // Pre:
    //       The type T implements the interface Comparable;
    //       x is a reference to a valid object of type T, or is null
    public boolean prune( T x) { . . . }

    // Restore the BST to an empty state; precisely the same as the state
    // created by the BST constructor.
    public void clear( ) { . . . }

    // Return true iff the two objects involved are both BSTs, have the
    // same physical structure, and store equal values in corresponding
    // nodes.  equals() should be tested using the data object’s equals()
    // method.
    // Pre:
    //       other is a reference to a valid BST object
    public boolean equals(Object other) { . . . }
}