CODEWITHSUNDEEP
cmemorymallocbinary-search-tree
meany
meany

Reputation: 25

Binary Search Tree malloc not giving enough memory for following nodes

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.

Upvotes: 2

Views: 2225

Answers (2)

Adeel Ahmed
Adeel Ahmed

Reputation: 1601

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);
}

Upvotes: 0

unwind
unwind

Reputation: 399949

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.

Upvotes: 9

Related Questions