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.

There's a lot of code that is not for inserting an element into a binary tree. — moooeeeep
– moooeeeep, Commented Mar 15, 2017 at 15:47

Chris Turner · Accepted Answer · 2017-03-15 16:04:55Z

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.

answered Mar 15, 2017 at 16:04

Chris Turner

8,1421 gold badge16 silver badges18 bronze badges

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

3 Comments

reswanth Over a year ago

the tree is not getting traversed if i use root only as the global variable and iam not passing any value to insert method the tree is getting traversed only for the first node.

Chris Turner Over a year ago

you are passing a value to insert - see this line: case 1:insert(root); - that's passing root by value. Maybe this explains the difference stackoverflow.com/questions/373419/…

Chris Turner Over a year ago

Also, root doesn't need to be global - it'd be better if it were declared locally in main

Collectives™ on Stack Overflow

Inserting element in binary tree

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related