Function to clear allocated memory is not working

I'm trying to make a DTC in C. This is the structure of the nodes:

typedef struct node {
    int value;
    struct node *lower;
    struct node *higher;
} node;

To free the memory allocated using malloc(), I've implemented this function:

void free_nodes(node*a) {
    if(a->higher != NULL) {
        free_nodes(a->higher);
    }
    if(a->lower != NULL) {
        free_nodes(a->lower);
    }
    if(a->higher == NULL && a->lower == NULL) {
        free(a);
    }
}

It takes the pointer to the root node as a parameter.

I tried to use recursion here but it does not seem to free all the nodes. It is only able to free two nodes (I checked using valgrind).

I tried to use recursion here but it does not seem to free all the nodes.

The current node (a) is freed only if its a->higherand a->lower are NULL. Since they are not set to NULL anywhere, a will not be freed.

Instead a should always be freed as long as it is itself not NULL.

void free_nodes(node*a) {
    if (a == NULL) {
        return; // nothing to do
    }
    free_nodes(a->higher); // no need to check for `NULL` here, it will be done in the recursive call
    free_nodes(a->lower);  // no need to check for `NULL` here, it will be done in the recursive call
    free(a);  // we know that a is not NULL since it was checked in the beggining
}

Note that none of the pointers are actually set to NULL after freeing them. For the sub nodes it does not really matter. But the root node should be set to NULL by the caller after calling free_nodes with it.

Alternatively you can change free_nodes to accept a node**a (pointer to pointer) and set it to NULL inside it. This will require using *a all over, which is a bit more cumbersome, but from a design point of view it has the advantage that it guarantees a pointer will not remain non-NULL after it was freed, so there's no risk of double-free.

A final note:
The body of free_nodes can also be written equivalently as:

if (a) {     // the same as `if (a != NULL)`
    free_nodes(a->higher); // no need to check for `NULL` here, it will be done in the recursive call
    free_nodes(a->lower);  // no need to check for `NULL` here, it will be done in the recursive call
    free(a);  // we know that a is not NULL since it was checked in the beggining
}

Which style is better is a matter of personal preference (I personally prefer the first version, when the edge case is handled first and the rest is unconditional).