Level order traversal line by line

Level order traversal line by line, is an print arrangement of tree nodes element. That is useful to see exact how many nodes are exist of tree by level order. See this example line by line nodes are display form top to bottom and left to right.

Level order traversal line by line

Here given code implementation process.

/*
  C Program 
  Level order traversal line by line

*/
#include<stdio.h>
#include<stdlib.h>
//structure of Binary Tree node
struct Node{
  int data;
  struct Node*left,*right;
};

struct Queue{
  int level;
  struct Node*element;
  struct Queue*next;
};

//Create a binary tree nodes and node fields (data,pointer) 
//And returning the reference of newly nodes
struct Node* insert(int data){
  //create dynamic memory to new binary tree node
  struct Node*new_node=(struct Node*)malloc(sizeof(struct Node));
  if(new_node!=NULL){
    //set data and pointer values
    new_node->data=data;
    new_node->left=NULL; //Initially node left-pointer is NULL
    new_node->right=NULL;//Initially node right-pointer is NULL
  }else{
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  //return reference
  return new_node;
  
}
//Create a Queue element and return this reference
struct Queue* enqueue(struct Node*tree_node){
  
  struct Queue*Queue_node=(struct Queue*)malloc(sizeof(struct Queue));
  if(Queue_node!=NULL){
      //set pointer values
      Queue_node->element=tree_node;
      Queue_node->next=NULL;
      
    }else{
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  return Queue_node;
}
//Remove Queue elements
void dequeue(struct Queue**front){
  if(*front!=NULL){
    struct Queue*remove=*front;
    *front=remove->next;
    remove->element=NULL;
    remove->next=NULL;
    free(remove);
    remove=NULL;
  }
}
//Display tree element level order by using line by line
void level_order(struct Node*node){

  if(node !=NULL){
    //make Queue pointers
    struct Queue*front=NULL,
                *tail=NULL;

    //get first node of tree
    front=enqueue(node);
    front->level=0;
    tail=front;
    int check_level=0;

    struct Node*temp=node;
    while(front!=NULL){
      temp=front->element;
      if(temp->left!=NULL){
        //add new left child node
        tail->next=enqueue(temp->left);
        tail->next->level=front->level+1;
        tail=tail->next;

      }if(temp->right!=NULL){
        //add new right child node
        tail->next=enqueue(temp->right);
        tail->next->level=front->level+1;
        tail=tail->next;
      }
      if(front->level!=check_level){
        //when new level node are coming
        check_level=front->level;
        printf("\n");
      }
      //display elements
      printf("%d ",temp->data );
      dequeue(&front); //remove element of queue
    }
    tail=NULL;
  }else{
    printf("Empty Linked List\n");
  }
}
int main(){

  struct Node*root=NULL;
  /*  Make A Binary Tree
  -----------------------
             1
           /   \
          2     3
         /     / \
        4     5   6
       /  \    \    \
      7     8   9    10
  */

  //Insertion of binary tree nodes
  root                    =insert(1);
  root->left              =insert(2);
  root->right             =insert(3);
  root->right->right      =insert(6);
  root->right->left       =insert(5);
  root->left->left        =insert(4);
  root->left->left->left  =insert(7);
  root->left->left->right =insert(8);
  root->right->left->right =insert(9);
  root->right->right->right =insert(10);
  //Display Tree elements
  level_order(root);
  return 0;
}

Output

1 
2 3 
4 5 6 
7 8 9 10
/*
   C++ Program 
+  Level order traversal line by line
*/
#include<iostream>
using namespace std;

//Structure of Binary Tree node
class Node{
public:
  int data;
  Node*left,*right;
  //make a tree node
  Node(int data){
    //assign field values
    this->data=data;
    left=right=NULL;
  }
};
class Queue
{

public:
  Node*element;
  Queue*next;
  int level;
  Queue(Node*element){
    this->element=element;
    this->next=NULL;
  }
};

class BinaryTree{
public:
  Node*root;
  BinaryTree();
  void level_order(Node*);
  Queue * enqueue(Node*);
  void dequeue(Queue**);
};

//set initial tree root to NULL
BinaryTree:: BinaryTree(){
  root=NULL;

}
//Add queue element
Queue * BinaryTree:: enqueue(Node*element){

  Queue *newNode=new Queue(element);
  if(newNode==NULL){
    cout<<"Memory overflow"<<endl;
  }
  newNode->element=element;
  newNode->next=NULL;

  return newNode;
}
//Remove a queue element
void  BinaryTree:: dequeue(Queue**head){
  if(*head!=NULL){
    Queue*temp=*head;
    *head=temp->next;
    temp->element=NULL;
    temp->next=NULL;
    delete temp;
    temp=NULL;
  }

}

//Display tree element level order by using line by line
void  BinaryTree:: level_order(Node*node){

  if(node !=NULL){
    //make Queue pointers
    Queue*front=NULL,
          *tail=NULL;

    //get first node of tree
    front=enqueue(node);
    front->level=0;
    tail=front;
    int check_level=0;

    Node*temp=node;
    while(front!=NULL){
      temp=front->element;
      if(temp->left!=NULL){
        //add new left child node
        tail->next=enqueue(temp->left);
        tail->next->level=front->level+1;
        tail=tail->next;

      }if(temp->right!=NULL){
        //add new right child node
        tail->next=enqueue(temp->right);
        tail->next->level=front->level+1;
        tail=tail->next;
      }
      if(front->level!=check_level){
        //when new level node are coming
        check_level=front->level;
        cout<<endl;
      }
      //display elements
      cout<<" "<<temp->data;
      dequeue(&front); //remove element of queue
    }
    tail=NULL;
  }else{
    cout<<"Empty Linked List"<<endl;
  }
}
int main(){

  BinaryTree obj;
  /*  Make A Binary Tree
  -----------------------
             1
           /   \
          2     3
         /     / \
        4     5   6
       /  \    \    \
      7     8   9    10
  */

  //insert node of binary tree 
  obj.root                    =new Node(1);
  obj.root->left              =new Node(2);
  obj.root->right             =new Node(3);
  obj.root->right->right      =new Node(6);
  obj.root->right->left       =new Node(5);
  obj.root->left->left        =new Node(4);
  obj.root->left->left->left  =new Node(7);
  obj.root->left->left->right =new Node(8);
  obj.root->right->left->right =new Node(9);
  obj.root->right->right->right =new Node(10);
  //Display Tree elements
  obj.level_order(obj.root);
  return 0;
}

Output

 1
 2 3
 4 5 6
 7 8 9 10
/* 
   Java Program 
+  Level order traversal line by line
 */


//Structure of Binary Tree node
class Node{
  public int data;
  public  Node left, right;
    //make a tree node
  public Node(int data){
        //assign field values
    this.data=data;
    left=right=null;
  }
}
class Queue
{

  public Node element;
  public Queue next;
  public int level;
  public  Queue(Node element){
    this.element=element;
    this.next=null;
  }

}

class BinaryTree{
  public Node root;
  Queue head, tail;
  //set initial tree root to null
  public BinaryTree(){
    root=null;
    head=null;
    tail=null;
  }
  public Queue enqueue(Node element){

    Queue  newNode=new Queue(element);

    if(head==null) head=newNode;
    if(tail==null) tail=newNode;
    else{
      tail.next=newNode;
      tail=newNode;
    }
    return newNode;

  }

  //Remove a queue element
  public void dequeue(){
    if(head!=null){
      Queue temp=head;
      if(head==tail){
        tail=null;
      }
      head=head.next;
      temp.element=null;
      temp.next=null;
      temp=null;
    }

  }
  //display Level order traversal line by line of binary tree
  public void levelOrder(Node node){

    if(node!=null){
      if(node !=null){
       
        Node temp=null;
        Queue hold=null;
        //get first node of tree
        hold=enqueue(node);
        hold.level=0;
        while(head!=null){
          temp=head.element;
          if(temp.left!=null){
            //add new left child node
            hold=enqueue(temp.left);
            hold.level=head.level+1;

          }if(temp.right!=null){
            //add new right child node
            hold=enqueue(temp.right);
            hold.level=head.level+1;
          }

           //display elements
          System.out.print("  "+temp.data);
          if(head.next!=null && head.next.level!=head.level){
            System.out.println(" ");
          }
              dequeue(); //remove element of queue
        }

      }else{
        System.out.println("Empty Binary Tree List\n");
      }

    }
  }
  public static void main(String[] arges){
    BinaryTree obj=new BinaryTree();
  /*  Make A Binary Tree
  -----------------------
           1
         /   \
        2     3
       /     / \
      4     5   6
     /  \    \    \
    7     8   9    10
  */

  //insert node of binary tree 
  obj.root                  =new Node(1);
  obj.root.left             =new Node(2);
  obj.root.right            =new Node(3);
  obj.root.right.right      =new Node(6);
  obj.root.right.left       =new Node(5);
  obj.root.left.left        =new Node(4);
  obj.root.left.left.left   =new Node(7);
  obj.root.left.left.right  =new Node(8);
  obj.root.right.left.right =new Node(9);
  obj.root.right.right.right=new Node(10);
    //Display Tree elements
    obj.levelOrder(obj.root);

    }
}

Output

  1 
  2  3 
  4  5  6 
  7  8  9  1
#Python Program 
#Level order traversal line by line
class Queue:
    def __init__(self,element):
      #Assign node value
      self.element=element
      self.next=None
      self.level=0
      
class Node:
    def __init__(self,data):
      #Assign node value
      self.data=data
      self.left,self.right=None,None


class BinaryTree:

    def __init__(self):
      #set initial tree pointer to null
      self.root=None
      self.head=None
      self.tail=None
    #add Queue elements
    def enqueue(self,node):
        newNode=Queue(node)
        if(self.head==None):
          self.head=newNode
        if(self.tail==None):
          self.tail=newNode
        else:
          newNode.level=self.head.level+1  
          self.tail.next=newNode
          self.tail=newNode
        #print("Node : {} Level: {}".format(newNode.element.data,newNode.level))  

    #Remove Queue Elements    
    def dequeue(self):
        if(self.head!=None):
          temp=self.head
          if(self.head==self.tail):
            self.tail=None

            
          self.head=self.head.next
          temp.element=None
          temp.next=None
          temp=None

    #Display tree element level Order form
    def levelOrder(self,node):
        if(node!=None):
          self.enqueue(node)
         
          while(self.head!=None):
            current=self.head.element
            if(current.left!=None):
              self.enqueue(current.left)
            if(current.right!=None):
              self.enqueue(current.right)
             
            print(current.data,end="  ")
            if(self.head.next!=None and self.head.next.level!=self.head.level):
              print("") 
            self.dequeue()


def main():
    #Make object of Binary Tree
    obj=BinaryTree()
  #   Make A Binary Tree
  #-----------------------
  #         1
  #       /   \
  #      2     3
  #     /     / \
  #    4     5   6
  #   /     / \   \
  #  7     8   9   10
  #
  #insertion of binary tree nodes
    obj.root = Node(1)
    obj.root.left = Node(2)
    obj.root.right = Node(3)
    obj.root.right.right = Node(6)
    obj.root.right.right.right = Node(10)
    obj.root.right.left = Node(5)
    obj.root.left.left= Node(4)
    obj.root.left.left.left= Node(7)
    obj.root.right.left.left = Node(8)
    obj.root.right.left.right= Node(9)
    #Display Tree elements
    obj.levelOrder(obj.root)

  

if __name__=="__main__":
  main()

Output

1  
2  3  
4  5  6  
7  8  9  10
/* 
   C# Program 
+  Level order traversal line by line
 */
using System;

//Structure of Binary Tree node
class Node{
  public int data;
  public  Node left, right;
  //make a tree node
  public Node(int data){
    //assign field values
    this.data=data;
    left=right=null;
  }
}
class Queue
{

  public Node element;
  public Queue next;
  public int level;
  public  Queue(Node element){
    this.element=element;
    this.next=null;
  }

}

class BinaryTree{
  public Node root;
  Queue head, tail;
  //set initial tree root to null
  public BinaryTree(){
    root=null;
    head=null;
    tail=null;
  }
  public Queue enqueue(Node element){

    Queue  newNode=new Queue(element);

    if(head==null) head=newNode;
    if(tail==null) tail=newNode;
    else{
      tail.next=newNode;
      tail=newNode;
    }
    return newNode;

  }

  //Remove a queue element
  public void dequeue(){
    if(head!=null){
      Queue temp=head;
      if(head==tail){
        tail=null;
      }
      head=head.next;
      temp.element=null;
      temp.next=null;
      temp=null;
    }

  }
  //display Level order traversal line by line of binary tree
  public void levelOrder(Node node){

    if(node!=null){
      if(node !=null){

        Node temp=null;
        Queue hold=null;
        //get first node of tree
        hold=enqueue(node);
        hold.level=0;
        while(head!=null){
          temp=head.element;
          if(temp.left!=null){
            //add new left child node
            hold=enqueue(temp.left);
            hold.level=head.level+1;

          }if(temp.right!=null){
            //add new right child node
            hold=enqueue(temp.right);
            hold.level=head.level+1;
          }

          //display elements
          Console.Write("  {0}",temp.data);
          if(head.next!=null && head.next.level!=head.level){
            Console.WriteLine(" ");
          }
          dequeue(); //remove element of queue
        }

      }else{
        Console.Write("Empty Binary Tree List\n");
      }

    }
  }
  public static void Main(){
    BinaryTree obj=new BinaryTree();
    /*  Make A Binary Tree
    -----------------------
             1
           /   \
          2     3
         /     / \
        4     5   6
       /  \    \    \
      7     8   9    10
    */

    //insert node of binary tree 
    obj.root                  =new Node(1);
    obj.root.left             =new Node(2);
    obj.root.right            =new Node(3);
    obj.root.right.right      =new Node(6);
    obj.root.right.left       =new Node(5);
    obj.root.left.left        =new Node(4);
    obj.root.left.left.left   =new Node(7);
    obj.root.left.left.right  =new Node(8);
    obj.root.right.left.right =new Node(9);
    obj.root.right.right.right=new Node(10);
    //Display Tree elements
    obj.levelOrder(obj.root);

  }
}

Output

  1 
  2  3 
  4  5  6 
  7  8  9  10


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved