CODEWITHSUNDEEP
c++insertbinary-search-tree
dustinos3
dustinos3

Reputation: 974

runtime error when trying to insert after a node has previously been removed in a BST

I get a runtime error when I try to insert a number after a number has been deleted previously from the binary search tree. I'm assuming that somewhere in the tree after a deletion, that there is a broken path, so when it goes to insert the error occurs. I'm not sure where I have gone wrong. I assume it would be in the remove function. Here are the insert and remove functions:

void BST::insert(int x)
{
    TreeNode * v = root;
    if (root == NULL)
    {
        root = new TreeNode(x);
        return;
    }
    if (x == v->key)
    {
        return;
    }
    while (x != v->key)
    {

        if (x < v->key)
        {
            if (v->left != NULL)
            {
                v = v->left;

            }
            else
            {
                v->left = new TreeNode(x);
                return;
            }
        }
        if (x > v->key)
        {
            if (v->right != NULL)
            {
                v = v->right;
            }
            else
            {
                v->right = new TreeNode(x);
                return;
            }
        }
    }
}

void BST::remove(TreeNode * & v, int x)
{
    if (v == NULL)
        return;
    if (x < v->key)
    {
        remove(v->left, x);
    }
    if (x > v->key)
    {
        remove(v->right, x);
    }
    if (x == v->key)
    {
        if (v->left == NULL && v->right == NULL)
        {
            delete v;
            return;
        }
        if (v->left == NULL)
        {
            TreeNode *temp = v;
            v = v->right;
            delete temp;
        }
        if (v->right == NULL)
        {
            TreeNode * temp = v;
            v = v->left;
            delete temp;
        }
        if (v->left != NULL && v->right != NULL)
        {
            TreeNode * u = v->right;
            while (u->left != NULL)
            {
                u = u->left;
            }
            v->key = u->key;
            remove(u, u->key);          
        }
    }
}

Upvotes: 0

Views: 87

Answers (1)

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32732

There are multiple issues with this code, and several ways to dereference an invalid pointer.

In remove, when you've found the matching key, if the node has no children you delete it but don't null out the pointer to the deleted node, leaving a dangling reference.

You have a couple of series of if statements, that should be else if instead. If v->left == NULL, you change v to point to the right node, then you compare this new value's right with NULL and could end up removing multiple nodes.

Upvotes: 1

Related Questions