I can't seem to delete the simplest case on a Binary Search Tree in C

Question

Hi,

I've posted about this last year because some university project and now I have to do it again (I never finished what I had to do last year). I've already looked at me previous code, all you guys answers on those questions, but still, I can't seem to understand this.

I'm not going to put all my questions in one long post, it just makes everything more confusing and I need to understand this once and for all.

I'm working with the simplest BST possible (just an integer for element) and I'm trying to delete a node from the tree in it's simplest cast, deleting a leaf.

The tree elements I'm testing with are inserted in the following order: 7 3 10 2 5 1 6 9 4 8

And the output from in-order printing is, of course: 1 2 3 4 5 6 7 8 9 10

This is my Tree structure:

typedef int TreeElement;

typedef struct sTree {
   TreeElement item;

   struct sTree *left;
   struct sTree *right;
} Tree;

And this is my delete function:

int delete(Tree **tree, TreeElement item) {
    if(!*tree) return 1;

    Tree *currPtr = *tree;
    Tree *prevPtr = NULL;

    while(currPtr) {
        if(item < currPtr->item) {
            prevPtr = currPtr;
            currPtr = currPtr->left;
        } else if(item > currPtr->item) {
            prevPtr = currPtr;
            currPtr = currPtr->right;
        } else {            
            if(!currPtr->left && !currPtr->right) {
                currPtr = NULL;
            }

            free(currPtr);

            return 0;
        }
    }

    return 1;
}

I can't understand why but this is not working... As far as I understand it, I'm searching for the element to delete correctly. When I find it, I check if this node is a leaf by checking the left and right child are "empty". Which they are for my test case (trying to delete node 1).

When try to delete node 1 with the code above, I'll still get the in-order printing as I posted above. If I remove the currPtr = NULL from the if(!currPtr->left && !currPtr->right) block, I'll get the following for the in-order printing: 0 2 3 4 5 6 7 8 9 10.

I'm not understanding any of this...

What I'm missing in the code above so I can correctly delete a node that is a leaf? This is the most simple case of deleting a node in a BST, yet, I'm having so much trouble doing it, it's driving me crazy.

Answer 1

In this case you are change the value holding the current pointer, rather than the value in the node pointing to it. What you would actually want is something like

int delete(Tree **tree, TreeElement item) {
if(!*tree) return 1;

Tree *currPtr = *tree;
Tree *prevPtr = NULL;
bool fromLeft = false;

while(currPtr) {
    if(item < currPtr->item) {
        prevPtr = currPtr;
        currPtr = currPtr->left;
        fromLeft = true;
    } else if(item > currPtr->item) {
        prevPtr = currPtr;
        currPtr = currPtr->right;
        fromLeft = false;
    } else {            
        if(!currPtr->left && !currPtr->right) {
            if( fromLeft )
               prevPtr->left = NULL;
            else
               prevPtr->right = NULL;
        }

        free(currPtr);

        return 0;
    }
}

return 1;
}

Answer 2

A binary tree is a recursively defined data type, and deletion is far easiest with a recursive function. I don't even want to try to debug your tricky iterative solution; the mistake you are making is not a minor code mistake; the mistake is that you are using the wrong ideas for the job.

Here is some completely untested code:

Tree *delete(item, tree) {
   if (tree == NULL)
     return tree;
   else if (item < tree->item)
     tree->left = delete(item, tree->left);
   else if (item > tree->item)
     tree->right = delete(item, tree->right);
   else { // here comes the only interesting case
     // if one child is NULL, move the other up
     // otherwise grab an item from one child and recurse
     Tree *answer;
     if (tree->right = NULL) {
       answer = tree->left;
       free(tree);
       return answer;
     } else if (tree->left == NULL) {
       answer = tree->right;
       free(tree);
       return answer;
     } else {
       tree->item = tree->left->item; // choice of left/right is     arbitrary
       tree->left = delete(tree->left->item, tree->left);
       return tree;
     }
   }
}