Deleting minimum node from BST results in segmentation fault C++

Question

I am trying to delete the minimum node from a BST. But I get a seg fault.

To my understanding, minimum node will have no children, hence deleting it would not result in desserted leftover subtree. I am unsure on how to remove a node from a BST, I saw some solution that uses free() instead of delete. Where did I go wrong?

Source code for testing: https://onlinegdb.com/kiOZQee3w

1. Codes are in bst.hpp
2. Constructor starts at line 23
3. insert function starts at line 96
4. delete_min function starts at line 142
5. min function starts at line 180 to 203

***Added some code in editing

void delete_min()
{
    Node* min_node = min();
    Node* min_parent = min_node->parent; //Added this
    
    if(!root)
    {
        return;
    }

    // If min is root (Added this)
    if(!root->left)
    {
        auto tmp = root;
        root = root->right;
        delete tmp;
        return;
    }

    min_parent->left = min_node->right; //Added this
    delete min_node;
    --size;    
}

Node* min()
{
    if(root == nullptr)
    {
        return root;
    }
    else
    {
        return min(root);
    }
}

Node* min(Node* node)
{
    while(node->left != nullptr)
    {
        node = node->left;
    } 
    return node;
}

Answer 1

At very first your assumption that the minimum node doesn't have children is wrong; it doesn't have a left child, but it might have a right child; consider the most simple case of the root node and one single child that's greater than:

  1
   \
    2

Then for removing a node you cannot just only delete it, but you need to adjust it's parent's left pointer, too – or the root pointer, if the root is the minimum node. You can simply set it to the minimum's right child (can either of another node or a null pointer).

Update according to the code code provided on online GDB (this version is not matching the version in the question!):

Node* min_node = min();
if(min_node->right != nullptr)
{
    min_node->parent->left = min_node->right;
}

delete min_node;

You need to update the parent's left child unconditionally – if there's no grandchild, you'll just copy the null pointer that way, which is fine, as there won't be a right child any more anyway (the only one gets deleted).

But if there's a grandchild you need to update its parent (which otherwise would remain pointing to the deleted node, thus get dangling!):

Node* min_node = min();
min_node->parent->left = min_node->right;
if(min_node->right)
{
    min_node->right->parent = min_node->parent;
}

delete min_node;

  For this, though, you need the parent node available, too, thus you need to adjust the lookup of the minimum appropriately unless your nodes contain a link to their respective parent, too. Assuming this not being the case then your iteration might look as follows:

void deleteMin()
{
    // special handling: empty tree
    if(!root)
    {
        return;
    }

    // special handling: minimum is root
    if(!root->left)
    {
        auto tmp = root;
        root = root->right;
        delete tmp;
        return;
    }

    // now look for the minimum as you had already, but keep
    // track of the parent node as well!
    auto parent = root;
    child = root->left;
    while(child->left)
    {
        parent = child;
        child = child->left;
    }
    // OK, minimum found; essential step: adjust its parent!
    parent->left = child->right; // works for both a child available or not
    // now can safely delete:
    delete child;
}