C - Error in Deleting an Entire BST

Question

I can't seem for the life of me figure out what the is wrong with my code in the deletion of a whole BST.

I figure since there doesn't seem to be a problem with this:

void emptyTree(BST **root){ 
    if((*root)!=NULL){
        emptyTree(&(*root)->left);
        emptyTree(&(*root)->right);
        free(*root);
    }
}

Then the whole problem lies with the initial entry of each node in the tree. Can anyone point out what's wrong here?

void insertNode(BST **root, BST *temp){
    if((*root)!=NULL){
        temp->parent = *root;   
        if(((*root)->value) < (temp->value))    
            insertNode(&(*root)->right,temp);
        else if(((*root)->value) > (temp->value)) 
            insertNode(&(*root)->left,temp);
        else if(((*root)->value) == (temp->value)){ 
            printf("The number %i is already in the tree.\n",temp->value);  
            return;
        }
    } else {
        *root = temp;
        printf("%i was added to the tree.\n",temp->value);
        return;
    }
}

void newNode(BST **root, int x){
    BST *newnode;

    newnode = (BST *)malloc(sizeof(BST));
    newnode->value = x;
    newnode->left = newnode->right = newnode->parent = NULL;

    insertNode(root,newnode);
}

It compiles, it runs, it does absolutely every function right(including one that deletes one node at a time). Except the 'Delete All'(emptyTree) one. It doesn't delete everything(?). It doesn't even show an error when I run through the emptyTree function. It only errors when I printf the whole tree.

Well, one thing could be that [in C you should not cast the return or `malloc`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — Some programmer dude, Sep 21 '14 at 11:03
You need to step through the code in your debugger to see what's going on - this is much more productive than trying to guess what's wrong by looking at the code (or asking others to do the same). — Paul R, Sep 21 '14 at 11:04
You state there is something wrong. How do you know that? Does it compile? Run? Delete files instead? — Jongware, Sep 21 '14 at 11:04
Can you also add a `main` that shows, for a few items, how you use `newNode` and `insertNode` as well as `emptyTree` that (1) compiles and (2) shows the problem? See [How to create a Minimal, Complete, and Verifiable example](http://stackoverflow.com/help/mcve). — Jongware, Sep 21 '14 at 11:44

score 2 · Accepted Answer · answered Sep 21 '14 at 12:03

The error occurs because you do free all data, but forget to indicate that your elements no longer contain valid data.
That is, after deleting, all elements' left and right members, and your own root itself still contain a value; they still contain the original values, but these no longer point to valid, allocated, memory.

The error does not directly occur within emptyTree because this works from the end nodes up to the top, and there is no reason to check "down". But as soon as you attempt to print root (and its descendants), you are accessing unallocated memory.

Insert

*root = NULL;

in your emptyTree function after

free(*root);

to fix it inside the emptyTree function, or set root to NULL after calling emptyTree.

Personally, I prefer the former, even though it's a minor overhead. That way, you only have a single function to delete a tree, instead of the recursive one plus a wrapper that also sets the root to NULL.

I wrote *root=NULL there a few mins after i posted this question, but I wasn't sure if it actually deallocated or if its just linking to NULL and thus losing the entire tree. Thank you for the clarity :) — Hopeless Noob, Sep 21 '14 at 12:59
Yes, you need both. `free(x)` marks the pointed-to memory as *free* but it does nothing to `x`. `x=NULL;` does the oppposite; *you* say that you don't need the pointer anymore, but the memory block stays allocated and cannot be free'd in any way. — Jongware, Sep 21 '14 at 13:10

C - Error in Deleting an Entire BST

1 Answers1