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-28T16:13:12.797

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 '12 at 16:13

answered Nov 28 '12 at 14:54

1-----1

1,373
8
26

that's right. your answer missed the fact to link the new node `curr` to the tree – MOHAMED Nov 28 '12 at 14:58
1

Thank you, I understand now! I think it's supposed to be *hd = curr; though. But otherwise yes this is correct. – Man Person Nov 28 '12 at 16:02
Don't you need to add `return;` to stop the recursion? – Yonatan Simson Mar 24 '16 at 07:25
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. – 1-----1 Mar 24 '16 at 09:47

score 5 · Answer 2 · edited May 23 '17 at 11:53

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 '17 at 11:53

Community

1
1

answered Nov 28 '12 at 14:50

unwind

391,730
64
469
606

MOHAMED · Answer 3 · 2012-11-28T15:48:54.023

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 '12 at 15:48

answered Nov 28 '12 at 14:51

MOHAMED

41,599
58
163
268

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. – unwind Nov 28 '12 at 15:36
yes you are right. In some platforms NULL is not 0. thx. answer updated – MOHAMED Nov 28 '12 at 15:48

dreamcrash · Answer 4 · 2020-11-20T20:14:23.963

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

Kash · Answer 5 · 2012-11-28T15:12:53.287

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 '12 at 15:12

answered Nov 28 '12 at 15:04

Kash

43
1
11

score 0 · Answer 6 · edited Mar 28 '14 at 08:56

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

Recursive Binary tree insertion

6 Answers6