Learn basic concept of c , c++ and python programming in regularcodes.com

Level order traversal line by line

Print level order traversal line by line of a given binary tree, without using recursion.

For example Given Binary tree are contain following nodes.

Result

Hint: User queue to solve this problem.

View pointers and nodes of tree.

Program for Print level order traversal line by line in c. using queue.

 
/*
  Help of this program we are learning how to 
  print level order traversal line by line.
  Using queue.
  Time complexity : O(n).
*/


/* Include header file*/
#include<stdio.h>
#include<stdlib.h>

/*Define struct of Binary Tree */
struct Tree{
  /*Data field*/
  int data;
  /*Pointer field*/
  struct Tree*left,*right;
};
/*Define struct of Queue */
struct Queue{
  int level;
  /*Pointer field*/
  struct Tree*link;
  struct Queue*next;
};


/*Function declaration section*/
struct Tree*create_node(int);
struct Tree* free_node(struct Tree*);
void queue_record(struct Tree*,struct Queue**,struct Queue**);
void dequeue(struct Queue**);
void enqueue(struct Tree*,struct Queue**,struct Queue**,int);
void empty_queue(struct Queue**);
void level_by_line(struct Queue*);

/*  Create newly Binary tree Node.*/
struct Tree*create_node(int value){
  /*Create memory block of size of struct Tree.*/
  struct Tree*new_node=(struct Tree*)malloc(sizeof(struct Tree));
  if(new_node!=NULL){
    new_node->data=value;
    new_node->left=new_node->right=NULL;
    return new_node;
  }else{
    printf("\n Memory overflow.");
    return NULL;
  }  
}

/*insert queue data */
void enqueue(struct Tree*temp,struct Queue**tail,struct Queue**head,int level){

  struct Queue*new_node=(struct Queue*)malloc(sizeof(struct Queue));
  if(new_node){

    new_node->link=temp;

    new_node->next=NULL;
    new_node->level=level;
    if(*head==NULL){
      *head=new_node;
    }
    if(*tail!=NULL){

      (*tail)->next=new_node;
    }
    *tail=new_node;
    
  }
  else{
    printf("\n Queue overflow");
  }
}

/* Free queue node */
void dequeue(struct Queue**head){

  struct Queue*remove=*head;
  if(remove!=NULL){
    remove->link=NULL;
    *head=remove->next;
    remove->next=NULL;
    free(remove);
    remove=NULL;
  }
}

/*perform queue operation*/
void queue_record(struct Tree*root,struct Queue**head,struct Queue**tail){

  if(root==NULL){
    printf("\n Empty Tree");
    return;
  }

  /*Fill first node of Queue*/
  enqueue(root,tail,head,0);

  struct Queue*auxiliary=*head;
  /*This loop execute until when auxiliary pointer are not NULL*/
  while(auxiliary!=NULL){
    if(auxiliary->link->left !=NULL){
      enqueue(auxiliary->link->left,tail,head,auxiliary->level+1);
    }
    if(auxiliary->link->right !=NULL){
      enqueue(auxiliary->link->right,tail,head,auxiliary->level+1);
    }   
    auxiliary=auxiliary->next;  
  }
}


/*Remove all element of queue*/
void empty_queue(struct Queue**head){
  while(*head!=NULL){
    dequeue(head);
  }
}

/*Print nodes in level by level of given bt(binary tree)*/
void level_by_line(struct Queue*temp){
  if(temp!=NULL){
    printf("\n Line by line binary tree nodes");
    int line=-1;
    while(temp!=NULL){
      if(line!=temp->level){
        printf("\n");
        line=temp->level;
      }
      printf("%4d",temp->link->data);
      temp=temp->next;
    }

  }else{
    printf("\n Empty Queue");
  }

}

/*Help of this function Free Binary Tree Nodes */
struct Tree* free_node(struct Tree*temp){

  if(temp){
    temp->left=free_node((temp->left));
    temp->right=free_node(temp->right);
    free(temp);
    temp=NULL;
  }
  return NULL;
}



/*Main function*/
int main(){
  
  /*Start execution*/

  /* Binary Tree struct pointer*/
  struct Tree*root=NULL;

  struct Queue*head=NULL,*tail=NULL;

  /*inserting following data*/
  root                      = create_node(1);
  root->left                = create_node(2);
  root->right               = create_node(3);
  root->left->left          = create_node(4);
  root->left->right         = create_node(5);
  root->right->right        = create_node(7);
  root->left->right->left   = create_node(9);
  root->right->left         = create_node(6);
  root->left->left->left    = create_node(8);
  root->left->right->left->right  = create_node(10);   

  queue_record(root,&head,&tail);
  
  level_by_line(head);

  /*Empty queue*/
  empty_queue(&head);

  /*Free Binary Tree Node*/
  free_node(root);

  return 0;
  /* End execution of program */
}

Output

View process