Freeing memory allocated for a Tree - C

Question

I have a tree defined like,

struct tree {
    char label[MAX_LENGTH];
    char value[MAX_LENGTH];
    struct tree *child;
    struct tree *next;
};

Now I need to free the memory allocated by this tree. I wrote the following code.

unsigned int tree_free(struct tree *root)
{
    struct tree *current = NULL, *next = NULL, *child = NULL;
    unsigned int freecnt = 0;

    current = root;
    while(current != NULL)
    {
        next = current->next;
        child = current->child;      
        xfree(current);
        freecnt += tree_free(child) + 1;
        current = next;
    }
    return freecnt;
}

This method returns the number of items it freed so that I can verify it against the number of allocations made. This code works. But I am not sure this is the correct way of doing things.

This is a suffix tree implementation. For items s,stack,over, overflow, stackoverflow the tree will look like

root
-s
--stack
---stackoverflow
-over
--overflow

Any suggestions to improve the code are welcome.

Answer 1

If you need to free a tree you need to walk it, so I think the code is correct. I would have done it the same way (recursively walk the tree, freeing the objects along the way). The only thing I would do differently is to run the xfree after the recursion (i.e. swap xfree(current); and freecnt += tree_free(child) + 1;). Because now you delete a node before you delete its child, but I feel that it would be better to delete the child before deleting the parent.

Also, you could get rid of the child variable as you use it only once, with a real need. Would save you sizeof(pointer) of stack space per recursion ;-)

Answer 2

That's a fairly good solution. You're using recursion for the children (which won't go too deep) but iteration for the siblings (which would go deep if you used recursion). Your code could certainly be more elegant as a recursion-only solution (calling tree_free for both child and next) but the risk of stack overflow would be greatly increased so I think you made the right choice there.

Having said that, there's no need for child at all if you re-arrange the order of your operations:

unsigned int tree_free (struct tree *root) {
    struct tree *current = NULL, *next = NULL;
    unsigned int freecnt = 0;

    current = root;
    while(current != NULL)
    {
        freecnt += tree_free (current->child) + 1;
        next = current->next;
        xfree (current);
        current = next;
    }
    return freecnt;
}

If you think the length of your sibling list won't be that large, you could try the elegant solution:

unsigned int tree_free (struct tree *root) {
    unsigned int freecnt;

    if (root == NULL) return 0;
    freecnt = tree_free (root->child) + tree_free (root->next);
    xfree (root);
    return freecnt + 1;
}

It's untested so I make no statement of warranty or fitness for purpose, especially since it's probably dangerous for your specific case of a large number of sibling links. I include it more as an indication of what's possible with recursion. My advice is to use the first one.