I wrote a recursive function in C to free memory allocations made by a program that generates a tree of nodes. However, I can’t work out how it works – but it does pass the check50. Perhaps I’ve not written it well enough for me to understand it.

I’ve tried following the debugger but I just cannot get my head around how it manages to traverse 3 generations of parents successfully.

I suppose my main questions are:

1. How does this function free from bottom to top of the ancestry tree? E.g. how and when does free(p) get called? Is it when return is called? I know it’s important not to orphan any nodes, but I don’t know how this is avoided here.

2. Following the debugger and stepping through the code, free(p) clearly isn’t called until it seems that a grandparent node is reached – e.g. free_family(p->parents[0]) has been called twice and then the subsequent call to p->parents[0] is NULL, before free(p) frees that stack from the call. I can’t get my head around how this works at all.

Apologies for the noob question – I’m new to coding and following CS50x currently.

I won’t post the entire code unless required, but each node is defined by the following code. There are 3 generations of these nodes. The last generation of parents receives NULL parent pointers.

typedef struct person
{
    struct person *parents[2];
    char alleles[2];
} person;

My recursive free function is:

// Free `p` and all ancestors of `p`.
void free_family(person *p)
{
    // TODO: Handle base case

    if (p == NULL)
    {
        return;
    }

    // TODO: Free parents recursively

    free_family(p->parents[0]);
    free_family(p->parents[1]);

    // TODO: Free child

    free(p);
}