C: How deallocate memory for spanning tree?

Question

I have a n-ary tree structure with only parents and children. The spantree itself holds only one node, the root. Then there are created nodes which are linked with other nodes or the root. Each node(root included) are allowed to have up to MAXCHILDREN children nodes. Here's the structure:

typedef struct node{
    unsigned int id;                    //every node has different id
    struct node* parent;                //points to parent node
    struct node* children[MAXCHILDREN]; //pointers to all children of this node
}node;

typedef struct spantree{
    node root;                          //root node
}spantree;

Visual picture:

        root
      ___O
     /  / \ 
    O  O   O 
          / \
         O   O

After I have created my tree I want to deallocate the whole thing but I am unsure on which way to do it. I can't start deallocating from the root because then the tree will get broken. So I imagine that I have to start from the leaves and going up to the root? But that means that I have to find the deepest leaves first, right? I feel quite confused on how to start.

I don't think it's neccesary but for insurance here's what I use everytime I need to make a new node:

node *newNode;
newNode=(node*)malloc(sizeof(node));
//then I modify it to my preferences

Answer 1

You need to check if the node you're freeing has children, and free them first if it does.

    void free_node( node *n ) {
    if(n) { 
      for(int i=0; i<MAXCHILDREN; i++)
        free_node(n->children[i]);
      free(n);
      }
    }

Answer 2

Recurse through the tree, call the recursive function first, then free memory.

void deleteNode(node * Node) {
  for (int i = 0; i < MAXCHILDREN; ++i) {
    if (node->children[i]) {
      deleteNode(node->children[i]);
      free(node->children[i]);
    }
  }
}

Answer 3

You're correct, you need to use your favorite traversal function to find the leaves, and then free those before freeing the parent nodes. Once the children have been freed, you basically have another leaf node that you can then free.

You'll need to use recursion. Enjoy!

Answer 4

You heard anything about POST-ORDER Traversing? You use the same technique to delete all of the nodes. This automatically deletes the parents after all their children are deleted.