/**
 * K_BST<T> implements a Binary Search Tree where the class itself
 * acts as the node (implicit node structure).
 *
 * This version extends K_AbstRecBinTree<T> to create a more constrained BST
 * structure, despite potential Liskov Substitution Principle violations.
 *
 * INVARIANT: A non-empty K_BST tree must always have non-null K_BST
 * objects as its left and right children; the children may be empty
 * subtrees.  An empty tree is defined by having null data as well as null
 * left and right children.
 *
 * BST INVARIANT:
 * 1. All values in the left subtree are less than the root's value.
 * 2. All values in the right subtree are greater than or equal to the
 *    root's value (allows duplicates).
 *
 * @param <T> The type of data stored, constrained to be Comparable,
 *            which is a stricter constraint than the superclass.
 */
public class K_BST<T extends Comparable<T>> extends K_AbstRecBinTree<T>
{
    // Instance variables are inherited from K_AbstRecBinTree<T>
    // and are accessible as 'protected' members.

    /**
     * Constructor initializes an empty BST object.
     * The superclass constructor sets data, left, and right to null.
     */
    public K_BST()
    {
        super(); // Calls K_AbstRecBinTree constructor
    }

    /** {@inheritDoc}
     *
     * Overrides the add method to enforce Binary Search Tree invariant.
     * Note: This method relies on dynamic binding: when adding to
     * this.left or this.right, the runtime object is a K_BST, so this
     * method is called recursively.
     *
     * @param value The value to be added.
     */
    @Override
    public void add(T value)
    {
        // Case 1: The current tree object is empty (the insertion point).
            // NEED CODE HERE !!!

        // Case 2: Tree is not empty, compare the new value with the
        // current node's data.
            // NEED CODE HERE !!!
    }

    /** {@inheritDoc}
     *
     * Overrides the remove method to enforce the Binary Search Tree invariant.
     */
    @Override
    public T remove(T itemToFind)
    {
        // NEED CODE HERE !!!
        return null;
    }

    /** Finds the leftmost non-empty node in the tree and returns the
     *  data that was in that node.
     */
    private T returnLeftmost()
    {
        // Return null if this node is empty (but this should never happen
        // unless the tree was empty to begin with).
        if ( isEmpty() )
        {
            return null;
        }

        // How do we know if this is the leftmost node?  If it is, return
        // that value.
        // NEED CODE HERE !!!

        // This node is not the leftmost; return its leftmost child.
        // We have to cast left to K_BST, because otherwise the compiler
        // thinks left is of type K_AbstRecBinTree, and that class doesn't
        // have a returnLeftmost method.
        return ((K_BST<T>)left).returnLeftmost();
    }


}