What is wrong with this simple C program?

[setuid_w00t]

#include <stdlib.h>

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

struct node *insert(int value, struct node *cur_root);

int main(int argc, char *argv[])
{
struct node *root;
root = insert(5, root);
printf("%d\n", root->value);
return 0;
}

struct node *insert(int value, struct node *cur_root)
{
if(cur_root == NULL)
{
cur_root = malloc(sizeof(struct node));
cur_root->value = value;
}
else if(value < cur_root->value)
cur_root->left = insert(value, cur_root->left);
else if(value > cur_root->value)
cur_root->right = insert(value, cur_root->right);
return cur_root;
}


I am trying to refresh myself on the small amount of C I know. I figured I would implement a rudemetary binary search tree. I haven't made it very far. The code compiles without any warnings or errors, but when I run it:
$ ./binstree
-1073743096

It should of course display the number 5. Any suggestions?

[vomjom]

You haven't initialized:
struct node *root; to NULL
You assume it's NULL in insert()

a proper first line for main() would be:
struct node *root = NULL;

[kmj]

yeah, duh. :)

[LiquidG]

This is more of a follow up question to your initial question, as I am trying to brush up on my C as well :)

If you're trying to create a binary search tree, wouldn't you need to initialize new *left and *right (depending on where each new node is inserted into the tree)? After inserting 5, the new node containing 5 should have *left & *right pointing to NULL, no? This initialization could occur in your 'struct node' definition I suppose.

[kmj]

bafalouk: the insert function actually does that for you. Notice the 'if' and 'else if' branches call insert again, which will allocate space for the left and right branches.

[CheeseLick]

All I did was initialize root to NULL and cast the returned pointer to a node * and it worked as expected.

[kmj]

as vomjom said in the second post of the thread. :D

[CheeseLick]

I saw that someone said to initialize the variable, but I didn't see that anyone has mentioned to cast the pointer returned by malloc().

Upon closer inspection, I never mentioned malloc() in my post, but that's what I was trying to say.

[ChefNinja]

Isn't CheeseLick the TSO mascot :\

[CheeseLick]

Sweet Jesus.

Yes. Yes, I was. I have been running the DoD and SOF2 servers on The-Space.net lately, though.

[ChefNinja]

Ahh, I love The-Space :)

I remember back when TSO was the The-Space Offensive, and the-space.net was THE CS server to play on :)


I played on the-space and AnglowBryce.net... you know Hael, don't you?

[l01yuk]

I didn't see that anyone has mentioned to cast the pointer returned by malloc().

The pointer returned my malloc shouldn't be cast. If you read the def for malloc it will return the suitable pointer type and doing so could hide the fact that some headers haven't been included.

What should have been done though is the return value from malloc checked to make sure it isn't NULL and error if it is.

[CheeseLick]

Cool.

I always thought that malloc() returned a void pointer which had to be cast to the correct type. Maybe Windows and Lunix are different like that.

[l01yuk]

Actually it's an ISO standard thing.

The pointer returned if the allocation
succeeds is suitably aligned so that it may be assigned to a pointer to any type of object
and then used to access such an object or an array of such objects in the space allocated
(until the space is explicitly deallocated).

See, no need to cast.

[ThurberMingus]

Here is the prototype for malloc, ISO:

void *malloc(size_t size);

It DOES return a pointer of the void type. However, it is true that an explicit cast is not required, though it does help to show forth your intentions in your code, avoiding possible errors.

Here is a reference for your reading pleasure:
http://www.gnu.org/manual/glibc-2.0.6/html_chapter/libc_3.html#SEC21

[{F}allen]

if you were going to typecast the result, would it be cast as (node) or as (node *) ?

[ThurberMingus]

Originally posted by {F}allen
if you were going to typecast the result, would it be cast as (node) or as (node *) ?

(node)

foo = (node) malloc(bar * sizeof(baz));

;-)

[l01yuk]

You want to use (node *).
You are trying to convert a pointer to an integer.

If you must cast then use (type *).

Also, use the object to give the size.

foo = malloc(bar * sizeof(*foo));

This means that if you ever change the type of foo you don't have to change the malloc statement too.

[ThurberMingus]

Originally posted by l01yuk
You want to use (node *).
You are trying to convert a pointer to an integer.

If you must cast then use (type *).

Also, use the object to give the size.

foo = malloc(bar * sizeof(*foo));

This means that if you ever change the type of foo you don't have to change the malloc statement too.

You know, I KNEW I would screw something up! I used to be really good with this stuff, but for some reason I missed that one. I know to do everything you said . . . it has been a while since I have used malloc or any casting or pointers.

[strags]

Originally posted by kmj
bafalouk: the insert function actually does that for you. Notice the 'if' and 'else if' branches call insert again, which will allocate space for the left and right branches.

The code is still wrong.
He needs to set ->left and ->right to NULL whenever he malloc's a new node.

Otherwise, let's see what happens on the second insertion.

First insertion: root is NULL, a new node is allocated, and value is copied across. left and right may contain uninitialised garbage.

Second insertion (let's suppose we insert 3). We will recurse, passing in cur_root->left as our new root. But this is a garbage pointer. Misery abounds.