Trying to delete a node from a binary search tree

Question

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.

deleting a pointer does not set it to NULL. Is that what you are expecting? — Neil Kirk
– Neil Kirk, Commented Sep 22, 2015 at 4:25
@NeilKirk I thought it did? So what would be a good alternative to make this NULL while at the same time deallocating the memory? — David Velasquez
– David Velasquez, Commented Sep 22, 2015 at 4:30
r is a local variable, so setting it to NULL won't set the pointer you originally copied it from to NULL. — Neil Kirk
– Neil Kirk, Commented Sep 22, 2015 at 4:35

1201ProgramAlarm · Accepted Answer · 2015-09-22 04:35:40Z

1

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.

answered Sep 22, 2015 at 4:35

1201ProgramAlarm

32.8k7 gold badges47 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

David Velasquez Over a year ago

If you can elaborate more because I'm not understanding your solution. I tried to do what you said to the best of my understanding but it still crashes.

1201ProgramAlarm Over a year ago

In the found loop, use previous = &r->left; r = r->left. If a leaf, delete r; *previous = null;. Only right child: *previous = r->right;. And you'll need to do something similar with minNode since the pointer to it will be dangling after you delete it.

Collectives™ on Stack Overflow

Trying to delete a node from a binary search tree

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related