Creating a binary tree but it doesn't work — tree is always null

Question

I am creating a code to insert the elements in tree, but tinsert function does not insert; what is wrong with my code? I have checked many times but tree is always NULL.

The code has only 2 functions: one to insert, and second to show it in preorder.

#include<stdio.h>
#include<stdlib.h>

struct btree {
    int val;
    struct btree *left;
    struct btree *right;
};

static int c=0;
typedef struct btree node;

void tinsert( node *n,int a)
{
    c++;
    printf("%d\n",c);
    if(n==NULL)
    {
        n=(node *)malloc(sizeof(node));
        n->left=NULL;
        n->right=NULL;
        n->val=a;
        //printf("adding root %d\n",n->val);
        //n=temp;
    }
    else if(a>=(n->val))
        tinsert(n->right,a);
    else
        tinsert(n->left,a);
    return ;
}

void preorder_display(node *n)
{
    if(n!=NULL)
    {
        printf("%d\n",n->val);
        preorder_display(n->left);
        preorder_display(n->right);
    }
    else
        printf("tree is null\n");
}

int main()
{
    //int N;
    //int num[100];
    //int i;
    node *ntree=NULL;

    tinsert(ntree,4);
    tinsert(ntree,6);
    tinsert(ntree,8);
    tinsert(ntree,1);

    printf("tree is \n");
    preorder_display(ntree);

    return 0;
}

Answer 1

tinsert works on a local copy of your ntree, it doesn't change the one in your main. You can fix it by passing a pointer to it (i.e.: double pointer, pointer to a pointer).

So your tinsert will look like this:

void tinsert( node **n,int a)

And in your main you'll call it like this:

tinsert(&ntree,4);

Of course, you'll need to adjust the code in tinsert to de-reference the pointer and access it correctly.

Or allocate the root node in your main.

Answer 2

you pass your root node ntree to tinsert function by value, so when when the function is done you will stay with original value of ntree which is NULL.
You better rewrite your function, so you will pass pointer to pointer

 void tinsert( node **n,int a)


 //and invocation is like that :

  tinsert(&ntree,4);

Answer 3

when you pass ntree from main to tinsert function, new copy is created to your node*n;

One way is to make use of pointer to pointer Or second solution is here:

Here is a solution:

#include<stdio.h>
#include<stdlib.h>

struct btree{
int val;
struct btree *left;
struct btree *right;
};

static int c=0;
typedef struct btree node;

node* tinsert( node *n,int a)
{
c++;
printf("%d\n",c);
  if(n==NULL)
{ 

   n=(node *)malloc(sizeof(node));
   n->left=NULL;
   n->right=NULL;
   n->val=a;

 //printf("adding root %d\n",n->val);
 //n=temp;
}
else if(a>=(n->val))
tinsert(n->right,a);
else
tinsert(n->left,a);

return n;
}



void preorder_display(node *n)
{
if(n!=NULL)
{
printf("%d\n",n->val);
preorder_display(n->left);
preorder_display(n->right);
}
else
printf("tree is null\n");
}




int main()
{
//int N;
//int num[100];
//int i;
node *ntree=NULL;



ntree=tinsert(ntree,4);
ntree=tinsert(ntree,6);
ntree=tinsert(ntree,8);
ntree=tinsert(ntree,1);

printf("tree is \n");
preorder_display(ntree);


return 0;
}

Answer 4

C supports the pass by value only. However, this does not prevent you from modifying the value of a variable from another function, because you can always refer to a variable using it's memory; and in C it's done through pointers, an abstraction representing a memory location.

When you pass a value to the function, the value of the actual parameter is copied to the value of formal parameter. Note that a pointer's value is the address it points to. So, this value is copied into the formal parameter. So the new pointer inside the function points to the exact same location your original variable. You can deference the pointer anytime to manipulate it's value.

Here, you are required to manipulate a pointer. So you pass a pointer-to-pointer to the function:

tinsert(&ntree,4);

In your function, you deference it to get your original pointer; like the following:

void tinsert(node **n, int a)
{
    //...
    *n = malloc(sizeof(node));
    //...
}