# free n-ary tree

This is a discussion on free n-ary tree within the C Programming forums, part of the General Programming Boards category; I'm having a hard time trying to free an N-ary tree, don't know if this is asking too much, but ...

1. ## free n-ary tree

I'm having a hard time trying to free an N-ary tree, don't know if this is asking too much, but can somebody please post a small and fast algorithm for that? or at least give me some guidelines...

thank you

2. Have you tried freeing it in the reverse order of how it was malloc'ed?

Think of the malloc'd nodes as if you pushed them onto a stack. (FILO). Now you want to pop them off that stack, and free them.

If you're still stuck, post up your code and tell us what has you stumped. My shirt pocket appears not to have an example of this, at this time.

3. Recursion should do the trick:
Code:
```clearNode(Node *n)
{
int i=0;
while(i < N)
{
if(n->leaf[i])
{
clearNode(n->leaf[i]);
free(n->leaf[i]);
}
i++;
}
free(n);
}```
Or something along that line.

4. Well since we've already got a code solution posted. I'll show a simpler alternative. However it intentionally contains at least two hidden bugs (so you still have to take the time to debug it if you wish to use it).
Code:
```void freeTree(Node *n)
{
if (n == NULL)
return;
for (int i=0; i<N; ++i);
freeTree(n->child[1]);
free(n);
}```

5. Done! Quite simple actually... ty

Code:
```void freeTree(Tree_str *Tree){
if(Tree){
freeTree(Tree->brother);
freeTree(Tree->son);
free(Tree);
}
}```

6. Do an in-order traversal deleting only leaves. You will have to create a temporary place holder for the next in-order node* before you delete it (because you cannot find the next in-order node for one that does not exist), which with a leaf that will be it's parent, and that parent will at some point end up as a leaf at which point it gets deleted.

Make sense? I promise it does work.

* alternately, you can do this recursively, but recursion is less efficient and prone to stack overflows on large trees. I just noticed that was your post above, which is recursive...this is a limitation!

Popular pages Recent additions