Inserting element in binary tree

Question

The code is for inserting an element in a binary tree using level order traversal. I'll first tell u how it works. It first goes through the nodes in each level and if there is any node which doesn't have both children it inserts the node as a child to that node and it use's queue for storing and retrieving the nodes addresses. My problem is that every time I call the create function the root value which is passed is always null even after inserting a node the root value is not changed and it's still a null. I am unable to figure out what's wrong in this. Can anyone help me out?

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

struct node
{
   int data;
   struct node *left,*right;
}*root;

struct queue
{
   int capacity,rear,front;
   struct node **qu;
};


void enqueue(struct queue *q,struct node *n)
{
   q->front=(++(q->front))%q->capacity;
   (q->qu)[q->front]=n;
   if(q->rear==-1)
   q->rear++;
}

struct node* dequeue(struct queue *q)
{
   struct node *temp;
   temp=q->qu[q->rear];
   if(q->front==q->rear)
   q->front=q->rear=-1;
   else
   q->rear=(++(q->rear))%q->capacity;
}

int isempty(struct queue *q)
{
   return(q->rear==-1);
}

struct queue* create(unsigned int capacity)
{
   struct queue *p;
   p=(struct queue*)malloc(sizeof(struct queue));
   p->capacity=capacity;
   p->front=p->rear=-1;
   p->qu=(struct node**)malloc(sizeof(struct node)*capacity);
   return p;
}


 void insert(struct node *root)
 {
    int n;
    struct node *p,*q;
    struct queue *tmp;
    p=(struct node*)malloc(sizeof(struct node));
    p->left=p->right=NULL;
    scanf("%d",&n);
    p->data=n;
    if(root==NULL)
    {
      root=p;
      return;
    }
    tmp=create(20);
    enqueue(tmp,root);
    while(isempty(tmp))
    {
      q=dequeue(tmp);
      printf("%d %d\n",p,root);
      if((!q->right)||(!q->left))
      {
          if(!q->right)
          q->right=p;
          else
          q->left=p;
          return;
      }
      else
      {
         enqueue(tmp,q->left);
         enqueue(tmp,q->right);
      }
    }
 }

 void traverse(struct node *root)
 {
   if(!root)
   return;
   traverse(root->left);
   printf("%d ",root->data);
   traverse(root->right);
 }

void main()
{
   int i,n;
   while(1)
   {
       printf("1.insert\n2.exit\n");
       scanf("%d",&n);
       switch(n)
       {
          case 2:goto end;
          case 1:insert(root);
       }
    }
    end:
    traverse(root);
 }

Thanks.

Answer 1

You've defined root as a global variable, but your insert function also defines it's own local version of root which takes precedence. Because you're passing root in by value rather than reference, changing it's value has no effect. You have two options on how to fix this.

• Pass root by reference

You change insert to be void insert(struct node **root) and then replace all instances of root in the function with (*root). You'll also need to pass a pointer to root when you call it - insert(&root)

• Return the new value of root

Change the return type to struct node * and make sure you return root at the end and at any point where you're already returning from the function. When you call it you'll assign the return value to root like root=insert(root)

Both are equally valid options.