Binary Search Tree malloc not giving enough memory for following nodes

Question

I've come up with a problem where I do not give enough memory to my node after the first one when I do, for example, firstNode = (node)malloc(sizeof(node)). The following is the structure of *node and the insert function that uses the malloc function.

typedef struct treeNode *node;

struct treeNode {
    node left;
    node right;
    int data;
};

node firstN;
node secondN;

node insert(int a, node t){
    if(t==NULL){
        t = (node)malloc(sizeof(node));
        t->data = a;
        t->left = NULL;
        t->right = NULL;
    } else {
        if(a < t->data){
            t->left = insert(a, t->left);
        }else if(a > t->data){
            t->right = insert(a, t->right);
        }
    }
    return t;
}

Here is the main() where I tested the inserting process with malloc (I did not use the insert function defined above, because I was still testing line by line in the main).

firstN=(node)malloc(sizeof(node)*10);
firstN->data=1;
firstN->right=NULL;
firstN->left=NULL;
firstN->right=(node)malloc(sizeof(node)*10);

Interesting thing for me is that while the above works, just normally doing (node)malloc(sizeof(node)) (without the multiply by 10) does not work for the second instance, firstN->right.

I wonder why the code is not giving enough memory, if that is the correct case.

score 9 · Accepted Answer · edited May 23 '17 at 12:12

9

This:

t = (node)malloc(sizeof(node));

is wrong, you're not allocating enough memory to hold the structure, just the pointer to it since node is an alias for "pointer to struct treeNode".

You need:

t = malloc(sizeof *t);

Notice how that is way simpler? The cast is a bad idea, so it should be removed. And the size was wrong, so let's have the compiler compute it.

For many (many) allocations where you're storing the result in some pointer p, the value of sizeof *p is the proper argument to malloc(). This doesn't hold if you're allocating arrays of course, then it's often n * sizeof *p for some expression n.

Also, using typedef to hide pointers is generally a bad idea in C, since the pointers matter and it quickly becomes confusing.

edited May 23 '17 at 12:12

Community

1
1

answered Nov 27 '12 at 07:36

unwind

391,730
64
469
606

oh wow that does look way way simpler. thanks a lot. but here is a follow up question, if you don't mind. Why can't we then do malloc(sizeof *node) instead? I tried this, and it didn't work. Also, I just tried compiling without the casting, and it would work unfortunately, saying that void * is not of type node.. :( – meany Nov 27 '12 at 07:46
1

@meany If the compiler complains about a missing cast, you're compiling as C++ instead of C. You can't write `malloc(sizeof *node)`, because `node` is a type, and not a pointer that you could dereference (although, the pointer `n` is _not_ dereferenced in `malloc(sizeof *n)`, the expression `*n` therein only serves to determine the type, and from that the required size). – Daniel Fischer Nov 27 '12 at 07:52
If it doesn't compile without the cast, then you're not using a C compiler. And you can't do `sizeof *node` because `*node` is not a valid expression because `node` is a type, not a value. – melpomene Nov 27 '12 at 07:52

score 0 · Answer 2 · answered Nov 27 '12 at 08:31

typedef struct treeNode {
    struct treeNode *left;
    struct treeNode *right;
    int data;
}node;

node *firstN;
node *secondN;

node *insert(int a, node *t){
    if(t==NULL){
        t = malloc(sizeof(node));
        t->data = a;
        t->left = NULL;
        t->right = NULL;
    } else {
        if(a < t->data){
            t->left = insert(a, t->left);
        }else if(a > t->data){
            t->right = insert(a, t->right);
        }
    }
    return t;
}

int main(void) {

    firstN = malloc(sizeof(node)); /* allocating ROOT Node */
    firstN->data = 1;
    firstN->right = NULL;
    firstN->left = NULL;

    /* why are you allocating RIGHT, it will automatically be allocated when you insert Node */
    //firstN->right = (node)malloc(sizeof(node)*10);
}

Binary Search Tree malloc not giving enough memory for following nodes

2 Answers2