why my c code that checks if a binary search tree is complete or not (using array for checking) causes memory leak problem according to Valgrind

Question

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node* left;
    struct node* right;
}node;


node* createNode(int n) {
    node* new = (node*)malloc(sizeof(node));
    new->value = n;
    new->left = NULL;
    new->right = NULL;

    return new;
}


void insert(node** root, int num) {
    if (*root == NULL) {
        node* newNode = createNode(num);
        *root = newNode;
    }
    else {
        node* newNode = createNode(num);
        if (newNode) {
            if ((*root)->value > num) {
                insert(&(*root)->left, num);
            }
            else if ((*root)->value < num) {
                insert(&(*root)->right, num);
            }
        }
    }
}


void BFSinsert(node* currentNode, int* array, int i) {
    if (!currentNode) {
        array[i] = -1;  // to indicate that it's empty
        return;
    }
    BFSinsert(currentNode->left, array, 2*i+1);
    BFSinsert(currentNode->right, array, 2*i+2);
    array[i] = currentNode->value;
}


int isCompleteBTree(int arr[], int n) {
    for (int i = 0; i <= n / 2 - 1; i++) {
        if (arr[i] == -1) return 0;  // Found a NULL node
        if (2 * i + 1 >= n || arr[2 * i + 1] == -1) return 0;  
        if (2 * i + 2 >= n || arr[2 * i + 2] == -1) return 0;
    }
    return 1;
}


int countNodes(node* root) {
    if (root == NULL) return 0;
    else return 1 + countNodes(root->left) + countNodes(root->right);
}


void freeTree(node* node) {
    if (!node) return;
    if (node->left) freeTree(node->left);
    if (node->right) freeTree(node->right);
    free(node);
}


int main (void) {
    node* root = NULL;
    insert(&root, 6);
    insert(&root, 4);
    insert(&root, 8);
    insert(&root, 3);
    insert(&root, 5);
    insert(&root, 7);
    insert(&root, 9);


    int nodeCount = countNodes(root);
    int* array = (int*)malloc(100 * sizeof(int));

    BFSinsert(root, array, 0);

    printf("Array contents: ");
    for (int i = 0; i < nodeCount; i++) {
        if (array[i] == -1) nodeCount ++;  // nodeCount doesn't count NULL nodes, but array put -1 for empty nodes in the lowest level
        printf("%d ", array[i]);
    }
    printf("\n");

    if (isCompleteBTree(array, nodeCount)) printf("The tree is complete.\n");
    else printf("The tree is incomplete.\n");

    freeTree(root);
    free(array);

    return 0;
}

I know there are better ways to check if a binary search tree is complete or not, but that's the way that I'm asked to use (an array filled like breadth-first search kind of order). I think the code should free all the allocated memory, but when checking it using Valgrind, it shows there are 240 bytes of definitely lost memory.

I tried to find the problem where I have dynamically allocated memory. Is there any logical problem or not? I guess there isn't.

Answer 1

Your insert function is:

void insert(node** root, int num) {
    if (*root == NULL) {
        node* newNode = createNode(num);
        *root = newNode;
    }
    else {
        node* newNode = createNode(num);    <---- LOOK HERE
        if (newNode) {
            if ((*root)->value > num) {
                insert(&(*root)->left, num);
            }
            else if ((*root)->value < num) {
                insert(&(*root)->right, num);
            }
        }
    }
}

Notice that I added <---- LOOK HERE at the line node* newNode = createNode(num);

Now the question is:

What do you do with this newly malloced node?

Okay, you save it in newNode but what do you do with newNode ?

Nothing!! It's just lost.

So you leak memory.

To fix it, it seems that you simply want to delete that line (and the following if)