BstNode* maxValueNode(BstNode* node)
{
    BstNode* current = node;

    /* সবচেয়ে রাইটে যে আছে সেটিই সবচেয়ে বড়  */

    while (current->right != NULL)
        current = current->right;

    return current;
}

BstNode* deleteNode(BstNode* root, int key)
{
    /* বেস কেস  */

    if (root == NULL)
    {
        return root;
    }

    /* যে ডাটাটি ডিলিট করবো তা রুটের ভ্যালু থেকে ছোট হলে সেটি রুটের লেফট সাবট্রিতে আছে */

    if (key < root->data)
    {
        root->left = deleteNode(root->left, key);
    }

    /* যে ডাটাটি ডিলিট করবো তা রুটের ভ্যালু থেকে বড় হলে সেটি রুটের রাইট সাবট্রিতে আছে */

    else if (key > root->data)
    {
        root->right = deleteNode(root->right, key);
    }

    /* ডাটাটি রুটের ভ্যালুর সমান হলে এটিই সেই ডাটা যেটি আমরা ডিলিট করতে চাচ্ছি */

    else
    {
        /* নোডের যদি চাইল্ড না থাকে বা একটি চাইল্ড থাকে */

        if (root->left == NULL)
        {
            BstNode* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            BstNode* temp = root->left;
            free(root);
            return temp;
        }

        /* নোডের দুটি চাইল্ড থাকলে তার লেফট সাবট্রিয়ের সবচেয়ে বড় ভ্যালুকে আমরা খুঁজে বের করবো 
           অথবা রাইট সাবট্রিয়ের সবচেয়ে ছোট ভ্যালুকে আমরা খুঁজে বের করবো
           এখানে আমরা লেফট সাবট্রিতে সার্চ দিয়েছি */

        BstNode* temp = maxValueNode(root->left);

        /* লেফট সাবট্রিয়ের সবচেয়ে বড় ভ্যালুই এখন আমাদের রুট হবে */

        root->data = temp->data;

        /* লেফট সাবট্রিয়ের সবচেয়ে বড় ভ্যালুটি যেহেতু আমাদের রুটে নিয়ে এসেছি 
           তাই যেখান থেকে ভ্যালুটি এনেছি সেটিকে ডিলিট করে দেবো */

        root->left = deleteNode(root->left, temp->data);
    }

    return root;
}