public class BST {
    /* Root of BST */
    private Node root;
    /* Number of nodes in BST */
    private int size;

    public BST() {
        this.root = null;
        this.size = 0;
    }

    /**
     * Is the BST empty?
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * Return root of BST
     */
    public Node getRoot() {
        return root;
    }

    /**
     * Return number of key-value pairs in BST
     */
    public int size() {
        return size;
    }

    /**
     * Does there exist a key-value pair with given key?
     */
    public boolean contains(int key) {
        return find(key) != null;
    }

    /**
     * Return value associated with the given key, or null if no such key exists
     */
    public String find(int key) {
        return find(root, key);
    }

    /**
     * Return value associated with the given key, or null if no such key exists
     * in subtree rooted at x
     */
    private String find(Node x, int key) {
        if (x == null) {
            return null;
        }
        if (key < x.key) {
            return find(x.left, key);
        } else if (key > x.key) {
            return find(x.right, key);
        } else {
            return x.val;
        }
    }

    /**
     * Insert key-value pair into BST. If key already exists, update with new
     * value
     */
    public void insert(int key, String val) {
        if (val == null) {
            remove(key);
            return;
        }
        root = insert(root, key, val);
    }

    /**
     * Insert key-value pair into subtree rooted at x. If key already exists,
     * update with new value.
     */
    private Node insert(Node x, int key, String val) {
        if (x == null) {
            size++;
            return new Node(key, val);
        }
        if (key < x.key) {
            x.left = insert(x.left, key, val);
        } else if (key > x.key) {
            x.right = insert(x.right, key, val);
        } else {
            x.val = val;
        }

        return x;
    }

    /**
     * Remove node with given key from BST
     */
    public void remove(int key) {
        if(root == null){
            return;
        }
        if(root.left != null && key < root.key){
            remove(root.left, root, key);
        }else if(root.right != null && key > root.key){
            remove(root.right, root, key);
        }else{
            if(root.key != key){
                System.out.println("There are no key with value : " + key);
                return;
            }
            if(root.left == null && root.right == null){
                root = null;
                size--;
            }else if(root.left != null && root.right == null){
                root = root.left;
                size--;
            }else if(root.left == null && root.right != null){
                root = root.right;
                size--;
            }else{
                removeTwoChildren(root);
            }
            //Code for removing root
        }
    } // dummy code
    /**
     * Removes node with given Key from BST
     * recursive help function for remove(int key)
     */
    private void remove(Node current, Node parent, int key) {
        if(current.left != null && key < current.key){
            remove(current.left, current, key);
        }else if(current.right != null && key > current.key){
            remove(current.right, current, key);
        }else{
            if(current.key != key){
                System.out.println("There are no key with value : " + key);
                return;
            }
            if(current.left == null && current.right == null){
                removeNoChild(parent, current);
            }else if(current.left != null && current.right == null){
                removeLeftChild(parent, current);
            }else if(current.left == null && current.right != null){
                removeRightChild(parent, current);
            }else{
                removeTwoChildren(current);
            }
        }
        return;
    }
    /**
     * Removes node with two children
     */
    private void removeTwoChildren(Node removedNode) {
        Node replacement = findreplacement(removedNode.left);   //Returns the largest node in the left subtree
        int newKey = replacement.key;
        String newVal = replacement.val;
        remove(replacement.key);
        removedNode.key = newKey;
        removedNode.val = newVal;
    }

    /**
     * Returnes replacement node for a removed node with two children
     */
    private Node findreplacement(Node n) {
        if(n.right == null){
            return n;
        }
        return findreplacement(n.right);
    }
    /**
     * Removes node with right child
     */
    private void removeRightChild(Node parent, Node current) {
        if(parent.right == current){
            parent.right = current.right;
        }else if(parent.left == current){
            parent.left = current.right;
        }
        size--;
    }
    /**
     * Removes node with left child
     */
    private void removeLeftChild(Node parent, Node current) {
        if(parent.right == current){
            parent.right = current.left;
        }else if(parent.left == current){
            parent.left = current.left;
        }
        size--;
    }
    /**
     * Removes node with no child
     */
    private void removeNoChild(Node parent, Node current) {
        if(parent.left == current){
            parent.left = null;
        }else if(parent.right == current){
            parent.right = null;
        }
        size--;
    }

    public PreorderIterator preorder() {
        return new PreorderIterator(root);
    }

    public LevelorderIterator levelorder() {
        return new LevelorderIterator(root);
    }
}