public class BSTMap<K extends Comparable<K>, V> implements SimpleMap<K, V> {
    private int size;
    Node<K, V> left;
    Node<K, V> right;
    Node<K, V> root;
    Node<K, V> current;
    Node<K, V> previous;

    class Node <K extends Comparable <K>, V>{
        protected Node<K, V> left;
        protected Node<K, V> right;
        protected Node<K, V> root;
        protected Node<K, V> current;
        protected Node<K, V> previous;

        public Node() {
            root = null;
            current = null;
            previous = null;
            left = null;
            right = null;

        }
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    public BSTMMap() {
        root = null;
        right = null;
        current = null;
        previous = null;
        left = null;
    }
    /**
     * isEmpty()
     * @return boolean value if the bst is empty or not. checks the node
     */
    @Override
    public boolean isEmpty() {
         if (root == null){
             return true;
         }
        return false;
    }

    /**
     * size()
     * @return returns the size of the tree as an int
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * if root is null, first instance of insert will become the root. otherwise, it will iterate through the tree and place
     * the keys appropriately depending on if it is greater or less. when current has reached null, it has reached the bottom of the tree
     * and will increment the size and create a new node at that location
     */
    @Override
    public void insert(K key, V value) throws KeyFoundException {
        int compare;
        Node<K,V> current = root;
        compare = key.compareTo(current.key);


        while (current != null && current.key != key) {
            if (compare < 0 ) {
                current = current.left;
                continue;
            } else if (compare > 0 ) {
                current = current.right;
                continue;
            }
        }


        if (current == null) {
            current.key = key;
            current.value = value;
        }
        if (current.key == key) {
            current.value = value;
        }
    }

    /**
     * Deletes a key from the bst, throws keynotfound if key is not found
     * Goes through multiple cases to make sure the tree is correctly balanced
     */
    @Override
    public void delete(K key) throws KeyNotFoundException {
        if (root == null) {
            throw new KeyNotFoundException();
        }
        Node<K,V> current = root;
        int compare;
        compare = key.compareTo(current.key);
        while (current.key != key) {
            if (compare < 0) {
                current = current.left;
                continue;
            } else if (compare > 0) {
                current = current.right;
                continue;
            } else if (compare == 0) {
                previous = current;
                if (current.left == null & current.right == null) {
                    current = null;
                }else if (current.left != null && current.right != null) {
                    current = current.right;
                    while(current.left != null) {
                        current = current.left;
                    }
                    previous.key = current.key;
                    previous.value = current.value;
                    current = null;

                }else if (current.left == null) {

                    current = current.right;
                    while(current.left != null){
                        current = current.left;
                    }
                    previous.key = current.key;
                    previous.value = current.value;
                    current = null;
                } else if (current.right == null) {
                    current = current.left;
                    while(current.right != null) {
                        current = current.right;
                    }
                    previous.key = current.key;
                    previous.value = current.value;
                    current = null;
                }
            } else {
                current = root;
            }
        }

        }

    /**
     * iteratively searches through the BST for a key, if value is null then there is no key to be found.
     * if it is not null, then it returns all instances of the key found
     */
    @Override
    public V search(K key) throws KeyNotFoundException {
        int compare;
        Node<K,V> current = root;

        //compare = key.compareTo(current.key);
        while (current != null && current.key != key) {
            if (key.compareTo(current.key) < 0) {
                if (current.left == null) throw new KeyNotFoundException();
                current = current.left;
                continue;
            }
            else if (key.compareTo(current.key) > 0) {
                if (current.right == null) throw new KeyNotFoundException();
                current = current.right;
                continue;
            }
        }
        if (key.compareTo(current.key) == 0) {
            return current.value;
        } else {
            throw new KeyNotFoundException();
        }
    }

    /**
     * searches for the key given and modifies it's value to the given value.
     * keynotfound if it is null
     */
    @Override
    public void modify(K key, V value) throws KeyNotFoundException {
        int compare;
        Node<K,V> current = root;
        compare = key.compareTo(current.key);
        while (current != null && current.key != key) {
            if (current == null) {
                throw new KeyNotFoundException();
            } else if (compare == 0) {
                current.value = value;
            } else if (compare < 0 ) {
                current = current.left;
                continue;
            } else if (compare > 0 ) {
                current = current.right;
                continue;
            }

        }
    }

}