[SilverMage]

Hello, I'm a bit curious as to why this code doesn't work for inserting a node into a BST

insertNode(struct node* n, int x)
{
    if(n != NULL)
    {
         n = (struct node*) malloc(sizeof(struct node));
         n->number = x;
         n->left = NULL;
         n->right = NULL;
    }
   
    else if(n->number > x)
         insertNode(n->left, x);
    else
         insertNode(n->right, x);

}

The compiler doesn't complain, but I always get a segmentation fault, so instead, I have to rely on pointers to pointers. It seems a bit strange, Can anyone explain why?

This post has been edited by SilverMage: 08 October 2012 - 05:54 AM

[aresh]

Look at line 3. You write if (n != NULL). Is that what you want to do? I think you want to check if (n == NULL) because you will allocate memory only if it is NULL, right?

[SilverMage]

Whoops, that's true, wrote it here wrong, but I tried it with the n==NULL, and still got the seg fault.

[Skydiver]

Post your updated code.

You have to tell us where the segfault is at. Just saying it segfaults without details is about as good as telling is it doesn't work.

Assuming that the only thing you fixed was the if statement as you stated is post #3, then the segfault should not be in your insertNode() function. On the other hand it will the source of a logical error. Remember that lines 12 and 14 are only passing in the pointers to left and right. These pointers will not be changed by line 5 in the lower levels of recursion.

[SilverMage]

Skydiver, on 08 October 2012 - 07:37 AM, said:

Post your updated code.

You have to tell us where the segfault is at. Just saying it segfaults without details is about as good as telling is it doesn't work.

Assuming that the only thing you fixed was the if statement as you stated is post #3, then the segfault should not be in your insertNode() function. On the other hand it will the source of a logical error. Remember that lines 12 and 14 are only passing in the pointers to left and right. These pointers will not be changed by line 5 in the lower levels of recursion.

insertNode(struct node* n, int x)
{
    if(n == NULL)
    {
         n = (struct node*) malloc(sizeof(struct node));
         n->number = x;
         n->left = NULL;
         n->right = NULL;
         printf("%s\n", root->string);
         printf("%s\n", n->string);
         //I place this to check whether the root and n were initialized
    }
   
    else if(n->number > x)
         insertNode(n->left, x);
    else
         insertNode(n->right, x);

}

I placed the printf methods in order to check the nodes, when I check n->string, it outputs just fine. However, when I check my root, I get a seg fault.

[Skydiver]

Your line 9 crashes because no where in the code you've post are you setting/updating the pointer to the root node.

Are you setting the root pointer elsewhere, or are you assuming a code call like this will update the root?

struct node * root = NULL;
insertNode(root, 25);

Given your current insertNode() method, root will not be updated.

[Salem_c]

http://www.dreaminco...to-binary-tree/
Note the extra level of indirection in this example.

> insertNode(n->left, x);
This does NOT change n->left.

[SilverMage]

Skydiver, on 08 October 2012 - 07:58 AM, said:

Your line 9 crashes because no where in the code you've post are you setting/updating the pointer to the root node.

Are you setting the root pointer elsewhere, or are you assuming a code call like this will update the root?

struct node * root = NULL;
insertNode(root, 25);

Given your current insertNode() method, root will not be updated.

Salem_c, on 08 October 2012 - 08:04 AM, said:

http://www.dreaminco...to-binary-tree/
Note the extra level of indirection in this example.

> insertNode(n->left, x);
This does NOT change n->left.

Skydiver, I have my root set that way, but why won't my method update the root?

Salem, I was able to get the method working that way, but it's got me curious as to why I have to use pointers to pointers instead of an intuitive way involving just the node or a pointer to it.

[Salem_c]

void foo ( int a ) {
  a = 42;
}
int bar ( void ) {
  return 42;
}
int main ( ) {
  int a = 0;
  foo(a);
  printf("%d\n", a );
  a = bar();
  printf("%d\n", a );
  return 0;
}

Do you understand why foo() doesn't work, and bar() does?

One way is to declare

struct node* insertNode(struct node* n, int x) {
  if ( n == NULL ) {
    n = malloc.....
  }
  return n;
}

Then do
n->left = insertNode(n->left, x);

Or you pass a pointer to the node itself (see your other thread).

Or you switch to C++, and use a reference instead.

[SilverMage]

Salem_c, on 08 October 2012 - 08:20 AM, said:

void foo ( int a ) {
  a = 42;
}
int bar ( void ) {
  return 42;
}
int main ( ) {
  int a = 0;
  foo(a);
  printf("%d\n", a );
  a = bar();
  printf("%d\n", a );
  return 0;
}

Do you understand why foo() doesn't work, and bar() does?

One way is to declare

struct node* insertNode(struct node* n, int x) {
  if ( n == NULL ) {
    n = malloc.....
  }
  return n;
}

Then do
n->left = insertNode(n->left, x);

Or you pass a pointer to the node itself (see your other thread).

Or you switch to C++, and use a reference instead.

Hmmm, Now I see why that tutorial told me to use a pointer to the node. Now that I see, the root is a pointer itself, so the method makes sense now. Thanks, Salem, I just wanted to understand the tutorial better