what does !temp->left mean in C?

Question

I am studying binary search trees right now, and I came across this code

void free_tree(Node* root) {
    // Deallocates memory corresponding
    // to every node in the tree.
    Node* temp = root;
    if (!temp)
        return;
    free_tree(temp->left);
    free_tree(temp->right);
    if (!temp->left && !temp->right) {
        free(temp);
        return;
    }
}

what does !temp mean in this context? Does it mean if temp == NULL? and does that mean !temp->left or !temp->right mean "if right of temp == NULL"? I'm kind of confused with this code in general.

I tried searching for related questions, but so far got no answers.

The checking of !temp is because the functions free_tree(temp->left) aren't checking if the values of temp->left are null. I'd suggest try writing on from scratch by yourself because everyone's C code implementations are quite different to each others. — Richard Bamford, Nov 27 '22 at 16:20
If that's the complete code to free a tree, I suspect it fails to free much of the tree and leaks memory like crazy. As currently posted, the only nodes it actually frees are those with no children. — Andrew Henle, Nov 27 '22 at 16:33
By the way I don't know if that your function or not but It wont free the whole tree only the leafs of it (the bottom nodes) and their parent nodes will keep pointing to them and might cause you program to get segmentation fault. you can fix that by discarding the "if (!temp->left && !temp->right)" statement and free the node after the calls to free_tree for the left and right nodes — shaked maman, Nov 27 '22 at 16:33

Vlad from Moscow · Accepted Answer · 2022-11-27T17:13:39.103

From the C Standard (6.5.3.3 Unary arithmetic operators)

5 The result of the logical negation operator ! is 0 if the value of its operand compares unequal to 0, 1 if the value of its operand compares equal to 0. The result has type int. The expression !E is equivalent to (0==E).

and (6.3.2.3 Pointers)

3 An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. 66) If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

So these if statements

if (!temp)

and

if (!temp->left && !temp->right) {

is equivalent to

if ( temp == NULL )

and

if ( temp->left == NULL && temp->right == NULL ) {

Pay attention to that your function is wrong. It frees only memory for nodes data members left and right of which are null pointers.

A correct function can look for example the following wat

void free_tree( Node *root ) 
{
    // Deallocates memory corresponding
    // to every node in the tree.
    if ( root != NULL )
    {
        free_tree( root->left );
        free_tree( root->right );

        free( root );
    }
}

Though it will be better to declare and define it the following way

void free_tree( Node **root ) 
{
    // Deallocates memory corresponding
    // to every node in the tree.
    if ( *root != NULL )
    {
        free_tree( &( *root )->left );
        free_tree( &( *root )->right );

        free( *root );
        *root = NULL;
    }
}

After calling the function the original pointer to the root node passed to the function by reference through pointer to it will be equal to NULL.

score 0 · Answer 2 · answered Nov 27 '22 at 16:39

what does !temp mean in this context? Does it mean if temp == NULL?

Here ...

    Node* temp = root;
    if (!temp)
        return;

... yes, it means exactly that. In boolean context, a value of pointer type evaluates to true if and only if it is non-NULL. That is, pointer != NULL. The ! operator computes the logical negation, so !pointer is equivalent to pointer == NULL.

and does that mean !temp->left or !temp->right mean "if right of temp == NULL"?

No. The -> operator has higher precedence than the ! operator, so an expression of the form !x->y is equivalent to !(x->y). From context, we can determine that temp->left and temp->right designate pointers, so !temp->left and !temp->right mean temp->left == NULL and temp->right == NULL, respectively.

what does !temp->left mean in C?

2 Answers2