Freeing memory from a binary tree in C-CodePudding

I looked at this answer and I am sure I'm using it correctly but my while loop never ends.

My code recursivly removes the bottom level of the tree. At least I think it does. Here's the code:

void freeTree(node *tree){
    printf("\n\n");
    printf("Free Tree\n");//Start here #1
    printf("%i\n", tree->number); //#2
    if(!tree){//The tree is not null so continue
        return;
    }
    while (tree)
    {
        if(tree->left){
            printf("Going Left\n");// why does it go here at the end? #4
            freeTree(tree->left);
        } else if (tree->right)
        {
            printf("Going right\n");
            freeTree(tree->right);
        } else if (tree->right == NULL && tree->left == NULL)//Check if bottom of the tree
        {
            printf("Freed: %i\n", tree->number);// #3
            tree = NULL;
            free(tree);
        }
        
    }
    
}

My output in my terminal looks like this:

Free Tree
5
Freed: 5
Going Left

I don't understand how after freeing the node in my while loop it tries to free the node by Going Left in the console.

What am I missing or messing up here?

CodePudding user response：

Let’s follow the steps of the while loop. First we check if the tree has a left node. Assuming it does we take pointer to the node and call the function on it. Then, assuming function finished successfully we skip other conditions and go through the loop again. This time the pointer to the left node is still there but the memory it points to is freed. That is our first bug – dangling pointer. Second bug is the infinite loop. Because the condition never changes when in the loop (left node pointer stays set). To mitigate both issues you should set the left node pointer to null right after calling the function on it.

Same would happen with the right node (assuming program does not get stuck on the left node.

And finally, if both nodes are null, the pointer to tree set to null leaving a memory leak. And then you call free on the null pointer (which is fine on it own).

Generally when working with tree-like structures one would either use recursion or a loop. Using both normally does not make much sense.

P.S. An interesting fact. It is possible to fix this program by only removing code - the best kind of fix.

CodePudding user response：

void freeTree(node *tree)
{
    if(!tree) return;
    freeTree(tree->left);
    freeTree(tree->right);
    free(tree);

}