C - Too much memory allocated with malloc

Question

I'm working on a project for school, I must create and put binary trees into a dynamic array. I specify that I'm working on Windows using GCC (GNU compiler).

typedef struct s_node * TN;
struct s_node {
    char * chain; //Name of the tree
    int occ; //Number of occurences
    int ht; //Tree's height
};
typedef struct s_binary_tree * TBA;
struct s_binary_tree {
    TN root;
    TBA stl; //Sub Tree Left
    TBA str; //Sub Tree Right
};

Firstly I'm allocating memory using malloc() to create an array with x square of binary trees and then I'm allocating the memory for the binary trees.

TBA create_Binary_Tree(char * chain, int occ, int number_letters) {
    TBA tree = malloc(sizeof(TBA));
    tree->root = malloc(sizeof(TN));
    tree->root->chain = malloc(sizeof(char) * (number_letters + 1)); //+1 for the '\0'

    *(tree->root->chain) = '\0';
    strcpy(tree->root->chain,chain);
    tree->root->occ = occ;
    tree->root->ht = 1;

    tree->stl = NULL;
    tree->slr = NULL;

    return tree;
}

TBA * create_Array_Binary_Tree(char * fileName) {
    FILE * file;
    file = fopen(fileName,"r");
    if(!file) {
        exit(EXIT_FAILURE);
    }

    int number_letters;
    fscanf(file,"%d",&number_letters); //number_letters is the number of square that I want to allocate
    TBA * arr = malloc(sizeof(TBA) * number_letters);
    char * letter = malloc(sizeof(char) * 256);
    int occ, i;


    for(i = 0; i < number_letters; i++) { //number_letters = 1 in our example
        fscanf(file,"%s %d",letter,&occ);
        *arr = create_Binary_Tree(letter,occ,number_letters);
    printf("--Adr = %p--\n"arr); //Print the adress
        arr++;
    }
    arr -= i; //Reset the arr pointer

    fclose(file);

    return arr;
}

My problem is when I'm calculating the size of the array, the program tells me that the array size x + 38 square.

int size_Array_Binary_Tree(TBA * arr) {
    int sz_arr = 0;

    while(*arr != NULL) {
printf("-T = %d\tAdr = %p-\n",sz_arr,arr); //Print the adress
    sz_arr++;
    arr++;
}

return sz_arr;
}

Terminal :

--Adr = 0000000000951430-- //1 square allocated
-T = 0  Adr = 0000000000951430- //The square allocated
-T = 1  Adr = 0000000000951438- //?
-T = 2  Adr = 0000000000951440- //?
-T = 3  Adr = 0000000000951448- //...
-T = 4  Adr = 0000000000951450-
-T = 5  Adr = 0000000000951458-
-T = 6  Adr = 0000000000951460-
-T = 7  Adr = 0000000000951468-
-T = 8  Adr = 0000000000951470-
-T = 9  Adr = 0000000000951478-
-T = 10 Adr = 0000000000951480-
-T = 11 Adr = 0000000000951488-
-T = 12 Adr = 0000000000951490-
-T = 13 Adr = 0000000000951498-
-T = 14 Adr = 00000000009514A0-
-T = 15 Adr = 00000000009514A8-
-T = 16 Adr = 00000000009514B0-
-T = 17 Adr = 00000000009514B8-
-T = 18 Adr = 00000000009514C0-
-T = 19 Adr = 00000000009514C8-
-T = 20 Adr = 00000000009514D0-
-T = 21 Adr = 00000000009514D8-
-T = 22 Adr = 00000000009514E0-
-T = 23 Adr = 00000000009514E8-
-T = 24 Adr = 00000000009514F0-
-T = 25 Adr = 00000000009514F8-
-T = 26 Adr = 0000000000951500-
-T = 27 Adr = 0000000000951508-
-T = 28 Adr = 0000000000951510-
-T = 29 Adr = 0000000000951518-
-T = 30 Adr = 0000000000951520-
-T = 31 Adr = 0000000000951528-
-T = 32 Adr = 0000000000951530-
-T = 33 Adr = 0000000000951538-
-T = 34 Adr = 0000000000951540-
-T = 35 Adr = 0000000000951548-
-T = 36 Adr = 0000000000951550-
-T = 37 Adr = 0000000000951558-
-T = 38 Adr = 0000000000951560- //?

The size returned should be 1, but it returns 39. Could you please help me?

EDIT : I removed the pointer from types and adapted the rest but the problem still occurs.

typedef struct s_node TN;
struct s_node {
    ...
};

typedef struct s_binary_tree TBA;
struct s_binary_tree {
    TN * root;
    TBA * stl;
    TBA * str;
};

TBA * create_Binary_tree(...) {
    TBA * tree = malloc(sizeof(TBA));
    tree->root = malloc(sizeof(TN));
    ...
    return tree;
}

TBA ** create_Array_Binary_Tree(...) {
    ...
    TBA ** arr = malloc(sizeof(TBA *) * number_letters);
    ...
    for(i = 0; i < number_letters; i++) {
        ...
        arr[i] = malloc(sizeof(TBA));
        arr[i] = create_Binary_Tree(...);
        ...
    }
    ...
    return arr;
}

Any idea?

Answer 1

There are several errors in this program:

TBA create_Binary_Tree(char * chain, int occ, int number_letters) {
    TBA tree = malloc(sizeof(TBA));
    ...
}

TBA is a pointer to a struct. When you allocate sizeof(TBA) you're asking to allocate as much memory as a pointer needs, which is just 4 bytes (32 bit) or 8 bytes (64 bit). You want to allocate space for your struct instead:

TBA tree = malloc(sizeof(struct s_binary_tree));

The same problem here:

tree->root = malloc(sizeof(TN));

should be:

tree->root = malloc(sizeof(struct s_node));

Only TBA * arr = malloc(sizeof(TBA) * number_letters); is actually correct.

Avoid strcpy.

Instead of doing messy pointer arithmetics like arr -= i;, use a second variable where you store either the original pointer or the one you like to modify.

You are not NULL terminating arr. After you allocate it, there may be junk in it. It's best to make sure to fill it with NULLs if you rely on that being a sentinel:

memset(arr, 0, sizeof(TBA) * number_letters);
// Or use `calloc`, `bzero`, ...

This may be the reason your size_Array_Binary_Tree is giving you a strange result.