CODEWITHSUNDEEP
c++nullbinary-search-tree
David Velasquez
David Velasquez

Reputation: 2366

Trying to delete a node from a binary search tree

I'm getting a memory error when I try to display my tree after a node was deleted.
This is my remove (delete) method:

void binarySearchTree::remove(int x, node * r)
{
    bool found = false;
    node * previous = NULL;

    if (root == NULL)
    {cout << "Tree is empty. Nothing to remove." << endl; return;}

    while (!found)
    {
        if (x < r->data)
        {
            previous = r;
            r = r->left;
        }
        else if (x > r->data)
        {
            previous = r;
            r = r->right;
        }
        else
            found = true;
    }


    if (r->left == NULL && r->right == NULL)        //case 1: node to be deleted is a leaf (no children)
    {
        delete r;
        return;
    }
    else if(r->left == NULL && r->right != NULL)    //case 2: node only has a right child
        previous->right = r->right;
    else if (r->left != NULL && r->right == NULL)   //case 2: node only has a left child
        previous->left = r->left;
    else
    {                                               //case 3: node has two children
        node * minNode = findMinNode(r->right);     //finds min node in the right sub tree
        r->data = minNode->data;
        delete minNode;
        return;
    }
    delete r;
}

My findMinNode method:

binarySearchTree::node * & binarySearchTree::findMinNode(node * r)
{
    if (r == NULL)      //if tree is empty
        return r;

    if (r->left == NULL && r->right == NULL)
        return r;
    else if (r->left != NULL)
        return findMinNode(r->left);
    else
        return findMinNode(r->right);
}

My display method (using preorder traversal):

void binarySearchTree::display(node * r)
{
    if (r == NULL)
        return;

    display(r->left);
    cout << r->data << endl;
    display(r->right);
}

I'm using a public display() method which then calls this private display(node * r) method.

I know the problem is when I use delete because when I stepped through the code and got to my display() method, when it checked to see if r== NULL on the node I just deleted, the address was not NULL with an address of 0x000000000 but instead had 0x000000001. Because of this my program would crash. I've never encountered this problem before. Any help would be greatly appreciated.

I should add that I inserted these values in this exact order: 10, 5, 34, 2, 8, 12, 25, 6, 18, 27, 38, 11. I was trying to remove the node with value 12 because it had two children.

Upvotes: 1

Views: 1212

Answers (1)

1201ProgramAlarm
1201ProgramAlarm

Reputation: 32727

When you delete a node you need to NULL out the pointer that points to it, which in your example can be root, previous->left, or previous->right. If you change previous to be a node ** and have it point at the previous pointer (initialized to &root) then you can just say *previous = null or *previous = r->right.

Upvotes: 1

Related Questions