Binary Tree level order Traversal using queues?

Question

Please help me to find the mistake in my code. In this program i have created a binary tree and i want to traverse in level order,using Queues.

My output is stuck after printing first parent root.I think there's some mistakes i have made in the Queue functions.But i'm not able to find any mistakes.

here is my code below:

---

                #include<stdio.h>
                #include<stdlib.h>
                struct node
                {
                    int data;
                    struct node *left,*right;
                };
                struct node* create_root(int data)
                {
                struct node *root=(struct node*)malloc(sizeof(struct node));
                    root->data=data;
                    root->left=root->right=NULL;
                    return root;
                }
                struct node* create_tree(int data,struct node *root)
                {
                    char ch;
                 if(root==NULL)
                        return create_root(data);

                     printf("\nEnter R/L of %d ? ",root->data);
                     fflush(stdin);
                     scanf("%c",&ch);
                    if(ch=='R' || ch=='r')
                        root->right=create_tree(data,root->right);
                    else
                        root->left=create_tree(data,root->left);

                 return root;
                }
                struct queue
                {
                    struct node *info;
                    struct queue *next;
                };
                struct queue *start=NULL;
                struct queue* enQueue(struct node *root)
                {
                    struct queue *new_node,*ptr;
                    new_node=(struct queue*)malloc(sizeof(struct queue));
                    if(start==NULL)
                        start=new_node;
                    else
                    {
                        ptr=start;
                        while(ptr!=NULL)
                        {
                                if(ptr->next==NULL)
                                {
                                    ptr->next=new_node;
                                    new_node->next=NULL;
                                }
                        }
                    }
                    new_node->info=root;
                    return start;
                }
                struct queue* deQueue()
                {
                 struct queue *temp;
                        if(start==NULL)
                        {
                            printf("\nEmpty!!!!!");
                            return;
                        }
                        temp=start;
                        if(start->next==NULL) start=NULL;
                        else start=start->next;
                        return temp;

                }
                int isEmpty()
                {
                    if(start==NULL)
                        return 1;
                    else
                        return 0;
                }
                void level_order(struct node *root)
                {
                    struct queue *ptr;
                    if(root==NULL)
                    {
                        printf("\nEmpty!!!!!");
                        return ;
                    }
                    start=enQueue(root);
                    while(!isEmpty())
                    {
                        ptr=deQueue();
                        printf("%d ",ptr->info->data);

                        if(ptr->info->left)
                            enQueue(ptr->info->left);
                        else if(ptr->info->right)
                            enQueue(ptr->info->right);

                    }
                }
                int main()
                {
                    int n=0,num;
                    struct node *root=NULL;
                    printf("\nEnter data:");
                    scanf("%d",&num);
                    root=create_tree(num,root);
                    while(n<5)
                    {
                     printf("\nEnter data:");
                     scanf("%d",&num);
                     create_tree(num,root);
                     n++;
                    }
                    level_order(root);
                    return 0;
                }

Answer 1

Your enqueue-function is broken: You continue the loop until ptr is NULL, but inside the loop you do not change ptr at all!

  while(ptr!=NULL)
    {
            if(ptr->next==NULL)
            {
                ptr->next=new_node;
                new_node->next=NULL;
            }
    }

Instead, you have to advance in the list with every iteration until you have reached its end:

    while(ptr!=NULL)
    {
            if(ptr->next==NULL)
            {
                ptr->next=new_node;
                new_node->next=NULL;
                break;
            }
            ptr = ptr->next;
    }

This should fix the endless loop.

Furthermore, you should move the initialization of new_node->next to directly after the malloc(), to have it initialized also in the case of start == NULL:

new_node=(struct queue*)malloc(sizeof(struct queue));
new_node->next = NULL;
if(start==NULL)
      start=new_node;

Answer 2

level_order should make recursive calls to itself, not to enqueue().