// Source: OpenDSA Data Structures and Algorithms Modules Collection: CHAPTER 12 BINARY TREES: https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/BST.html

// Binary Search Tree implementation
class BST<E extends Comparable<E>> {
    private BSTNode<E> root; // Root of the BST
    private int nodecount; // Number of nodes in the BST

    // constructor
    BST() {
        root = null;
        nodecount = 0;
    }

    // Reinitialize tree
    public void clear() {
        root = null;
        nodecount = 0;
    }

    // Insert a record into the tree.
    // Records can be anything, but they must be Comparable
    // e: The record to insert.
    public void insert(E e) {
        root = inserthelp(root, e);
        nodecount++;
    }

    private BSTNode<E> inserthelp(BSTNode<E> rt, E e) {
        if (rt == null)
            return new BSTNode<E>(e);
        if (rt.value().compareTo(e) >= 0)
            rt.setLeft(inserthelp(rt.left(), e));
        else
            rt.setRight(inserthelp(rt.right(), e));
        return rt;

    }

    // Remove a record from the tree
    // key: The key value of record to remove
    // Returns the record removed, null if there is none.
    public E remove(E key) {
        E temp = findhelp(root, key); // First find it
        if (temp != null) {
            root = removehelp(root, key); // Now remove it
            nodecount--;
        }
        return temp;
    }


    // Get the maximum valued element in a subtree
    private BSTNode getmax(BSTNode rt) {
        if (rt.right() == null)
            return rt;
        return getmax(rt.right());
    }

    // Delete the maximum valued element in a subtree
    private BSTNode<E> deletemax( BSTNode<E> rt){
        if( rt.right() == null)
            return rt.left(); // null or the left child
        rt.setRight(deletemax(rt.right()));
        return rt;
    }

    /** Remove a node with key value k
        @return The tree with the node removed */
    private BSTNode<E> removehelp(BSTNode<E> rt, E key) {
        if (rt == null) return null;
        if (rt.value().compareTo(key) > 0)
            rt.setLeft(removehelp(rt.left(), key));
        else if (rt.value().compareTo(key) < 0)
            rt.setRight(removehelp(rt.right(), key));
        else { // Found it
            if (rt.left() == null)
                // Scenarios 1 (leaf node) and 2 (1 child)
                return rt.right();
            else if (rt.right() == null)
                // Scenario 2 (1 (left) child)
                return rt.left();
            else { // Two children
                BSTNode<E> temp = getmax(rt.left());
                rt.setValue(temp.value());
                rt.setLeft(deletemax(rt.right()));
            }
        }
        return rt;
    }

    // Return the record with key value k, null if none exists
    // key: The key value to find
    public E find(E key) {
        return findhelp(root, key);
    }

    private E findhelp(BSTNode<E> rt, E key) {
        if (rt == null)
            return null;
        if (rt.value().compareTo(key) > 0)
            return findhelp(rt.left(), key);
        if (rt.value().compareTo(key) == 0)
            return rt.value();
        else
            return findhelp(rt.right(), key);

    }


    // Return the number of records in the dictionary
    public int size() { return nodecount; }

}