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);
      }
    }