9 Replies - 647 Views - Last Post: 08 October 2012 - 08:46 AM Rate Topic: -----

#1 SilverMage  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 43
  • Joined: 11-October 10

How come an insert to a binary tree struct doesn't work this way

Posted 08 October 2012 - 05:53 AM

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


Is This A Good Question/Topic? 0
  • +

Replies To: How come an insert to a binary tree struct doesn't work this way

#2 aresh  Icon User is offline

  • It's a 16-Bit World!
  • member icon

Reputation: 273
  • View blog
  • Posts: 4,176
  • Joined: 08-January 12

Re: How come an insert to a binary tree struct doesn't work this way

Posted 08 October 2012 - 05:56 AM

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?
Was This Post Helpful? 0
  • +
  • -

#3 SilverMage  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 43
  • Joined: 11-October 10

Re: How come an insert to a binary tree struct doesn't work this way

Posted 08 October 2012 - 06:01 AM

Whoops, that's true, wrote it here wrong, but I tried it with the n==NULL, and still got the seg fault.
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3662
  • View blog
  • Posts: 11,466
  • Joined: 05-May 12

Re: How come an insert to a binary tree struct doesn't work this way

Posted 08 October 2012 - 07:37 AM

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.
Was This Post Helpful? 0
  • +
  • -

#5 SilverMage  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 43
  • Joined: 11-October 10

Re: How come an insert to a binary tree struct doesn't work this way

Posted 08 October 2012 - 07:52 AM

View PostSkydiver, 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.
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3662
  • View blog
  • Posts: 11,466
  • Joined: 05-May 12

Re: How come an insert to a binary tree struct doesn't work this way

Posted 08 October 2012 - 07:58 AM

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.
Was This Post Helpful? 0
  • +
  • -

#7 Salem_c  Icon User is online

  • void main'ers are DOOMED
  • member icon

Reputation: 1764
  • View blog
  • Posts: 3,421
  • Joined: 30-May 10

Re: How come an insert to a binary tree struct doesn't work this way

Posted 08 October 2012 - 08:04 AM

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.
Was This Post Helpful? 0
  • +
  • -

#8 SilverMage  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 43
  • Joined: 11-October 10

Re: How come an insert to a binary tree struct doesn't work this way

Posted 08 October 2012 - 08:15 AM

View PostSkydiver, 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.



View PostSalem_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.
Was This Post Helpful? 0
  • +
  • -

#9 Salem_c  Icon User is online

  • void main'ers are DOOMED
  • member icon

Reputation: 1764
  • View blog
  • Posts: 3,421
  • Joined: 30-May 10

Re: How come an insert to a binary tree struct doesn't work this way

Posted 08 October 2012 - 08:20 AM

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.
Was This Post Helpful? 0
  • +
  • -

#10 SilverMage  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 43
  • Joined: 11-October 10

Re: How come an insert to a binary tree struct doesn't work this way

Posted 08 October 2012 - 08:46 AM

View PostSalem_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
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1