// A utility function to delete a given key in BST
// NOTE THAT ROOT IS PASSED BY REFERENCE TO THE FUNCTION
void BinarySearchTree::delete_(TreeNode* &root, int key) {
    // base case
    if(root == NULL) return;

    // if the given key is greater than the root node, recur for the right subtree
    if(key > root->val) delete_(root->right, key);

    // if the given key is less than the root node, recur for the left subtree
    else if(key < root->val) delete_(root->left, key);

    // key found
    else {
        // Case 1: node to be deleted has no children (it is a leaf node)
        if(root->left == NULL and root->right == NULL) {
            delete (root);
            root = NULL;
        }

        // Case 2: node to be deleted has two children
        else if(root->left and root->right) {
            // find its inorder predecessor node
            TreeNode *pred = in_predecessor(root->left);

            // swap the values of the predecessor node & the current node
            swap(root->val, pred->val);

            // recursively delete the predecessor. Note that the
            // predecessor will have at most one child (left child)
            delete_(root->left, key);
        }

        // Case 3: node to be deleted has only one child
        else {
            // choose the child node
            TreeNode *child = (root->left) ? root->left : root->right;
            TreeNode *tmp = root;
            root = child;

            delete (tmp);
            tmp = NULL;
        }
    }
}