Thread: Binary Search Tree deletion

I'm writing an iterative delete method for my BST class. I'm a little confused on what to do when I've found the node and I want to delete it. I've developed this small code and I've removed the other sections of code so I can show the problem I'm having.

The question I have is... should I delete curr as I'm doing? Or should I simply set it to NULL? I'm pretty sure I have to delete the current node, but if I do, the results aren't correct. If I just make current NULL, it's fine. I'm pretty sure my other functions are correct. Any help is appreciated.

Code:

// code for 2 children and zero children here (which I haven't written)
...
...

// code for the case when there is only one child
// curr points to the node being deleted
else {
    if (curr == root) {
        // update root to be the child
        root = (curr->left != NULL) ? curr->left : curr->right;
        delete curr;
        curr = NULL;
    }
}

Did you use new to create the nodes? If yes, then you need to delete them when you are done.

My guess is that there are other places that point at the node being deleted. If you delete that node, those other places cause a failure. If you just null it out, then the other places still point at valid memory. The solution would be to make sure you delete the node once and null out all pointers to it.

Also note that your comment says that you are deleting the child of the current node, but the actual code is deleting the current node and setting the root to the child.

Ah yes... I made sure that all the other pointers were set properly and set the current's data members (left, right, data) equal to NULL and then deleted current. That seems to be working just fine. Thanks Daved.