How to free a tree struct using double pointer?

Question

I have to free a tree and set his root to NULL using a particular function. I tried to use a recoursive method. But if I compile i get some warnings about "incompatible pointer type" and I'm not able to resolve it. This is the struct:

typedef struct node {
int key; 
struct node *left, *mid, *right;
} node_t;

And here the function. The first line cannot be changed:

void free_tree (node_t ** root){
if(root != NULL){
    free_tree((*root)->left);
    free_tree((*root)->mid);
    free_tree((*root)->right);
    free(*root);
    }
return;
}

Any help would be appreciated

Answer 1

Your function expected a pointer to a pointer-to-node. You're giving it a pointer-to-node three times in your recursive calls. Further, you're not validating that the pointer-to-pointer, and the pointer it points to, are non-null; you're only validating the former.

In short, your function should look like this:

void free_tree (node_t ** root)
{
    if(root && *root)
    {
        free_tree(&(*root)->left);
        free_tree(&(*root)->mid);
        free_tree(&(*root)->right);
        free(*root);
        *root = NULL;
    }
}

The last functional line is optional, but frankly it's pointless to do this with pointers-to-pointers unless you're going to do that anyway, as it sets the caller's pointer to NULL after obliterating the tree. Given a properly built tree, your caller should deliver the address of the tree root when destroying the entire tree, as:

node_t *root = NULL;

// ... build tree ...

free_tree(&root);

// root is now NULL; tree is destroyed