andre andre - 3 months ago 8
C Question

Deallocating binary-tree structure in C

I have a linked list, I guess a tree looks like this:
enter image description here

-> grandma
-> dad
-> me
-> sister
-> niece
-> brother
-> uncle
-> cousin


and I have a struct as following

struct Node{
Node *parent;
Node *next;
Node *child;
}


How would I free that linked list?

My idea is to do a depth first search and deallocate each node?

Answer

Recursive depth-search

Your idea of DFS is right. It is a good way to dealocate binary-tree memory:

remove(node):
    if node is null: return

    //else
    remove(left node)
    remove(right node)

    free(node)

Iterative solution

http://codegolf.stackexchange.com/questions/478/free-a-binary-tree
Since you don't want to use any recursive solution, there you can find well-described iterative one.

Comments