Recursive Binary tree insertion

Question

So I'm trying to insert a value into a binary tree using this recursive function:

void add(node* *hd, int v){
node* curr = *hd;
if(curr == NULL){
    curr = (node*)malloc(sizeof(node));
    curr->value = v;
}else{
    if(v < curr->value){
        add(&curr->left, v);
    }else{
        add(&curr->right, v);
    }
}
}

It doesn't seem to be working, and I just don't understand why I can't do something like this. How would I go about fixing it?

1-----1 · Accepted Answer · 2012-11-28 16:13:12Z

6

You need to initilize the pointers, as they probably will be set to whatever you get when allocating space. Right now when you pass add(&curr->left, v); curr->left may not be a pointer somewhere but it is still not NULL;

void add(node* *hd, int v){
    node* curr = *hd;
    if(curr == NULL){
        curr = malloc(sizeof(node));
        curr->left = curr->right = NULL;
        curr->value = v;
        *hd = curr; // from Mohamed KALLEL
    }else{
        if(v < curr->value){
            add(&curr->left, v);
        }else{
            add(&curr->right, v);
        }
    }
}

edited Nov 28, 2012 at 16:13

answered Nov 28, 2012 at 14:54

1-----1

1,46310 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

MOHAMED Over a year ago

that's right. your answer missed the fact to link the new node curr to the tree

Man Person Over a year ago

Thank you, I understand now! I think it's supposed to be *hd = curr; though. But otherwise yes this is correct.

Yonatan Simson Over a year ago

Don't you need to add return; to stop the recursion?

1-----1 Over a year ago

No as we are looking for a node which is empty to insert at, thus when we reach if(curr == NULL) we will allocate the memory, set the pointers and then the recursion stops(reaches the end of the function) as it no longer calls add() as it is the other branch which was not taken.

Community · Accepted Answer · 2017-05-23 11:53:17Z

5

Your new node is not being "hooked up" correctly, since you're just storing the pointer in the local variable curr, instead of writing it to *hd to change the caller's pointer.

Also, don't cast the return value of malloc() in C.

edited May 23, 2017 at 11:53

CommunityBot

11 silver badge

answered Nov 28, 2012 at 14:50

unwind

402k64 gold badges492 silver badges620 bronze badges

Comments

MOHAMED · Accepted Answer · 2012-11-28 15:48:54Z

2

if(curr == NULL){
    curr = malloc(sizeof(node));
    curr->right = NULL;
    curr->left = NULL;  // From ks6g10 in order to initialize right and left to NULL
    curr->value = v;
    *hd = curr; // add this
}

BTW use calloc instead of malloc. it initializes your node memory to 0

edited Nov 28, 2012 at 15:48

answered Nov 28, 2012 at 14:51

MOHAMED

44k62 gold badges178 silver badges293 bronze badges

2 Comments

unwind Over a year ago

No point whatsoever in using calloc(); the only content it works for (the integer) is immediately overwritten. Note that calloc() can not be relied on to set pointers to NULL correctly.

MOHAMED Over a year ago

yes you are right. In some platforms NULL is not 0. thx. answer updated

dreamcrash · Accepted Answer · 2020-11-20 20:14:23Z

1

Another way to add in the binary tree recursively can be done like this:

node *add(node *hd, int v) {
   node* curr = NULL;

   if(!hd){
      curr = malloc(sizeof(node));
      curr->value = v;
      curr->left = NULL;
      curr->right = NULL;
      return curr;
   }
   else {
     if(v < curr->value)
        curr->left = add(curr->left,v);
     else 
        curr->right = add(curr->right,v);  
  }
  return hd;
}

edited Nov 20, 2020 at 20:14

answered Nov 28, 2012 at 15:03

dreamcrash

52.6k26 gold badges114 silver badges138 bronze badges

Comments

Kash · Accepted Answer · 2012-11-28 15:12:53Z

0

You need to initialize left and right pointers of your newly formed node with NULL and let your hd point to that node.

void add(node* *hd, int v){
node* curr = *hd;
if(curr == NULL){
    curr = malloc(sizeof(node));
    curr->value = v;
    curr->left=curr->right=NULL;
    *hd = curr;

}else{
    if(v < curr->value){
        add(&curr->left, v);
    }else{
        add(&curr->right, v);
    }
}
}

edited Nov 28, 2012 at 15:12

answered Nov 28, 2012 at 15:04

Kash

431 silver badge11 bronze badges

Comments

Warlord · Accepted Answer · 2014-03-28 08:56:44Z

0

I did it like this:

void insert(int data, node *&cur)
{
    if (cur == NULL)
    {
        cur = (struct node*) malloc(sizeof(struct node));
        cur->data = data;
        cur->left = NULL;
        cur->right = NULL;              
    }
    else
    {
        if (data > cur->data)
        {
            insert(data, cur->right);
        }
        else
        {
            insert(data, cur->left);
        }
    }
}

edited Mar 28, 2014 at 8:56

Warlord

2,82418 silver badges21 bronze badges

answered Mar 28, 2014 at 8:34

evan singh

1

Collectives™ on Stack Overflow

Recursive Binary tree insertion

6 Answers 6

4 Comments

Comments

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

4 Comments

Comments

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related