Level order traversal in spiral form

print binary tree node in Level order traversal in spiral form. That sequence is start to root node of tree, and (left to right) and after that (right to left) are printed level in top to bottom of binary tree.

Level order traversal in spiral form

Here given code implementation process.

/*
  C Program 
+ Level order traversal in spiral form

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

struct Stack{
  struct Node*element;
  struct Stack*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 stack element and return this reference
struct Stack* push(struct Node*tree_node){
  
  struct Stack*stack_node=(struct Stack*)malloc(sizeof(struct Stack));
  if(stack_node!=NULL){
      //set pointer values
      stack_node->element=tree_node;
      stack_node->next=NULL;
    
    }else{
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }
  return stack_node;
}
//Remove stack elements
struct Stack* pop(struct Stack**top){
  if(*top!=NULL){
    struct Stack*remove=*top;
    *top=remove->next;
    remove->element=NULL;
    remove->next=NULL;
    free(remove);
    remove=NULL;
    return *top;
  }
}
//Display tree element level order in spiral form
void spiral_level(struct Node*node){

    if(node !=NULL){
      //make stack pointer
      struct Stack*top1=NULL,*top2=NULL,*current_node=NULL,*new_node=NULL;

      struct Node*temp=node;
      top1=push(temp);
      current_node=top1;
      while(current_node!=NULL){
        //get current node reference of stack element
        temp=current_node->element; //this is binary tree element
        
        if(current_node==top1){
          //insert node from right to left
          //in Second stack
          if(temp->right!=NULL){
            new_node=push(temp->right);
            new_node->next=top2;
            top2=new_node;
          }
          if(temp->left!=NULL){
            new_node=push(temp->left);
            new_node->next=top2;
            top2=new_node;
          }
        }else {
          //Insert node from left to right
          //in first stack
          if(temp->left!=NULL){
            new_node=push(temp->left);
            new_node->next=top1;
            top1=new_node;
          }
          if(temp->right!=NULL){
            new_node=push(temp->right);
            new_node->next=top1;
            top1=new_node;
          }

        }
        

        if(current_node==top1){
           //when remove first stack element
          current_node=pop(&top1);
        }else{
          //when remove second stack element
          current_node=pop(&top2);
        }
        
        //When currently current pointer is NULL, then check it which stack are not empty, 
        //if non empty stack is exist then assign this top node reference to top node of stack
        if(current_node==NULL&&top1!=NULL) current_node=top1; //when first stack are not empty
        else if(current_node==NULL && top2!=NULL) current_node=top2;//when second stack are not empty
        
        //Display binary tree node value
        printf("  %d",temp->data);
      }
    }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
  */

  //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->right =insert(7);
  root->right->left->right =insert(8);
  root->right->right->right =insert(9);
  //Display Tree elements
  spiral_level(root);
  
  return 0;


}

Output

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

//ure 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 Stack{
public:
  Node*element;
  Stack*next;
  Stack(Node *node){
    element=node;
    next=NULL;
  }
};
class BinaryTree{
public:
  Node*root;
  Stack*top;
  BinaryTree();
  Stack* push( Node*);
  Stack* pop( Stack**);
  void spiral_level();
};

//set initial tree root to NULL
BinaryTree:: BinaryTree(){
  root=NULL;
  top=NULL;
}
//Create a stack element and return this reference
Stack* BinaryTree:: push( Node*tree_node){

  Stack*stack_node=new Stack(tree_node);
  if(stack_node!=NULL){
    //set pointer values
    stack_node->element=tree_node;
    stack_node->next=NULL;

  }else{
    cout<<"Memory Overflow"<<endl;

  }
  return stack_node;
}
//Remove stack elements
Stack* BinaryTree:: pop( Stack**top){
  if(*top!=NULL){
   Stack*remove=*top;
   *top=remove->next;
   remove->element=NULL;
   remove->next=NULL;
   delete remove;
   remove=NULL;
   return *top;
 }
}
//Display tree element level order in spiral form
void BinaryTree:: spiral_level(){

  if(root !=NULL){
    //make stack pointers
    //need two stack
    Stack*top1=NULL,*top2=NULL,*current_node=NULL,*new_node=NULL;

    Node*temp=root;
    top1=push(temp);
    current_node=top1;
    while(current_node!=NULL){
      //get current node reference of stack element
      temp=current_node->element; //this is binary tree element
      
      if(current_node==top1){
        //insert node from right to left
        //in Second stack
        if(temp->right!=NULL){
          new_node=push(temp->right);
          new_node->next=top2;
          top2=new_node;
        }
        if(temp->left!=NULL){
          new_node=push(temp->left);
          new_node->next=top2;
          top2=new_node;
        }
      }else {
        //Insert node from left to right
        //in first stack
        if(temp->left!=NULL){
          new_node=push(temp->left);
          new_node->next=top1;
          top1=new_node;
        }
        if(temp->right!=NULL){
          new_node=push(temp->right);
          new_node->next=top1;
          top1=new_node;
        }

      }
      

      if(current_node==top1){
         //when remove first stack element
        current_node=pop(&top1);
      }else{
        //when remove second stack element
        current_node=pop(&top2);
      }
      
      //When currently current pointer is NULL, then check it which stack are not empty, 
      //if non empty stack is exist then assign this top node reference to top node of stack
      if(current_node==NULL&&top1!=NULL) current_node=top1; //when first stack are not empty
      else if(current_node==NULL && top2!=NULL) current_node=top2;//when second stack are not empty
      
      //Display binary tree node value
      cout<<"  "<<temp->data;
    }
  }else{
    cout<<"Empty Linked List"<<endl;
  }


}
int main(){

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

  //insertion of binary tree nodes
  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->right =new Node(7);
  obj.root->right->left->right =new Node(8);
  obj.root->right->right->right =new Node(9);
  //Display Node elements
  obj.spiral_level();
  return 0;
}

Output

  1  2  3  6  5  4  7  8  9
/* 
Java Program 
Level order traversal in spiral form
 */

//Structure of Binary Tree node
class Node{

  int data;
  Node left, right;
    //make a tree node
  public Node(int data){
      //Assign field values
    this.data=data;
    left=right=null;
  }
}
//structure of stack Class
class Stack{

  Node element;
  Stack next;
  Stack(Node node){
    element=node;
    next=null;
  }
}

class BinaryTree{

  public Node root;
  private Stack top;
  public BinaryTree(){
    //set initial tree root to null
    root=null;
    top=null;
  }
//Create a stack element and return this reference
Stack push( Node tree_node){

  Stack stack_node=new Stack(tree_node);
  if(stack_node!=null){
    //set pointer values
    stack_node.element=tree_node;
    stack_node.next=null;

  }else{
   System.out.print("Memory Overflow\n");

  }
  return stack_node;
}
//Remove stack elements
public Stack pop(Stack top){
  if( top!=null){
   Stack remove= top;
    top=remove.next;
   remove.element=null;
   remove.next=null;
   
   remove=null;
   return  top;
 }
return  top;

}
//Display tree element level order in spiral form
public void spiralLevel(){

  if(root !=null){
    //make stack pointers
    //need two stack
    Stack top1=null, top2=null, currentNode=null, newNode=null;

    Node temp=root;
    top1=push(temp);
    currentNode=top1;
    while(currentNode!=null){
      //get current node reference of stack element
      temp=currentNode.element; //this is binary tree element
      
      if(currentNode==top1){
        //insert node from right to left
        //in Second stack
        if(temp.right!=null){
          newNode=push(temp.right);
          newNode.next=top2;
          top2=newNode;
        }
        if(temp.left!=null){
          newNode=push(temp.left);
          newNode.next=top2;
          top2=newNode;
        }
      }else {
        //Insert node from left to right
        //in first stack
        if(temp.left!=null){
          newNode=push(temp.left);
          newNode.next=top1;
          top1=newNode;
        }
        if(temp.right!=null){
          newNode=push(temp.right);
          newNode.next=top1;
          top1=newNode;
        }

      }
      

      if(currentNode==top1){
         //when remove first stack element
        currentNode=pop(top1);
        top1=currentNode;
      }else{
        //when remove second stack element
        currentNode=pop(top2);
        top2=currentNode;
      }
      
      //When currently current pointer is null, then check it which stack are not empty, 
      //if non empty stack is exist then assign this top node reference to top node of stack
      if(currentNode==null&&top1!=null) currentNode=top1; //when first stack are not empty
      else if(currentNode==null && top2!=null) currentNode=top2;//when second stack are not empty
      
      //Display binary tree node value
     System.out.print("  "+temp.data);
    }
  }else{
   System.out.print("Empty Linked List\n");
  }


}
  public static void main(String[] args){
    //Make object of Binary Tree
    BinaryTree obj=new BinaryTree();

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

    //insertion of binary tree nodes
    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.right =new Node(7);
    obj.root.right.left.right =new Node(8);
    obj.root.right.right.right =new Node(9);
    //Display Node elements
    obj.spiralLevel();

  }
}

Output

  1  2  3  6  5  4  7  8  9
#Python Program 
#Level order traversal in spiral form

 
class Node:
    def __init__(self,data):
      #Assign node value
      self.data=data
      self.left,self.right=None,None

class Stack:
    def __init__(self,data):
      #Assign node value
      self.element=data
      self.next=None
class BinaryTree:

    def __init__(self):
      #set initial tree root to None
      self.root=None
      


  
    #Create a stack element and return this reference
    def push(self,tree_node):

      stack_node=Stack(tree_node)
      if(stack_node!=None):
        #set pointer values
        stack_node.element=tree_node
        stack_node.next=None

      else:
        print("Memory Overflow")

      
      return stack_node
    
    #Remove stack elements
    def pop(self, top):
      if(top!=None):
       remove= top
       top=remove.next
       remove.element=None
       remove.next=None
       
       remove=None
       
     
      return  top

    
   #Display tree element level order in spiral form
    def spiralLevel(self):

      if(self.root !=None):
        #make stack pointers
        #need two stack
        top1=None
        top2=None
        currentNode=None
        newNode=None

        temp=self.root
        top1=self.push(temp)
        currentNode=top1
        while(currentNode!=None):
          #get current node reference of stack element
          temp=currentNode.element#this is binary tree element
          
          if(currentNode==top1):
            #insert node from right to left
            #in Second stack
            if(temp.right!=None):
                newNode=self.push(temp.right)
                newNode.next=top2
                top2=newNode
            
            if(temp.left!=None):
                newNode=self.push(temp.left)
                newNode.next=top2
                top2=newNode
            
          else :
            #Insert node from left to right
            #in first stack
            if(temp.left!=None):
                newNode=self.push(temp.left)
                newNode.next=top1
                top1=newNode
                        
            if(temp.right!=None):
                newNode=self.push(temp.right)
                newNode.next=top1
                top1=newNode
            

          
          

          if(currentNode==top1):
            #when remove first stack element
            currentNode=self.pop(top1)
            top1=currentNode
          else:
            #when remove second stack element
            currentNode=self.pop(top2)
            top2=currentNode
          
          
          #When currently current pointer is None, then check it which stack are not empty, 
          #if non empty stack is exist then assign this top node reference to top node of stack
          if(currentNode==None and top1!=None):
            currentNode=top1#when first stack are not empty
          elif(currentNode==None  and  top2!=None):
            currentNode=top2#when second stack are not empty
          
          #Display binary tree node value
          print(temp.data,end="  ")
        
      else:
        print("Empty Linked List")
      


    

def main():
    #Make object of Binary Tree
    obj=BinaryTree()


    """   Make A Binary Tree
    -----------------------
               1
             /   \
            2     3
           /     / \
          4     5   6
           \    \    \
            7    8    9
    """

   #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.left = Node(5)
    obj.root.left.left  = Node(4)
    obj.root.left.left.right = Node(7)
    obj.root.right.left.right = Node(8)
    obj.root.right.right.right = Node(9)
   #Display Node elements
    obj.spiralLevel()


if __name__=="__main__":
  main()

Output

1  2  3  6  5  4  7  8  9
//C# Program
//Level order traversal in spiral form
using System;
//Structure of Binary Tree node
public 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;
    }
}
//structure of stack Class
class Stack{

    public Node element;
    public Stack next;
    public Stack(Node node){
        element=node;
        next=null;
    }
}

class BinaryTree{

    public Node root;

    public BinaryTree(){
        //set initial tree root to null
        root=null;

    }
    //Create a stack element and return this reference
    Stack push( Node tree_node){

        Stack stack_node=new Stack(tree_node);
        if(stack_node!=null){
            //set pointer values
            stack_node.element=tree_node;
            stack_node.next=null;

        }else{
            Console.WriteLine("Memory Overflow");

        }
        return stack_node;
    }
    //Remove stack elements
    public Stack pop(Stack top){
        if( top!=null){
            Stack remove= top;
            top=remove.next;
            remove.element=null;
            remove.next=null;

            remove=null;
            return  top;
        }
        return  top;

    }
    //Display tree element level order in spiral form
    public void spiralLevel(){

        if(root !=null){
            //make stack pointers
            //need two stack
            Stack top1=null, top2=null, currentNode=null, newNode=null;

            Node temp=root;
            top1=push(temp);
            currentNode=top1;
            while(currentNode!=null){
                //get current node reference of stack element
                temp=currentNode.element; //this is binary tree element

                if(currentNode==top1){
                    //insert node from right to left
                    //in Second stack
                    if(temp.right!=null){
                        newNode=push(temp.right);
                        newNode.next=top2;
                        top2=newNode;
                    }
                    if(temp.left!=null){
                        newNode=push(temp.left);
                        newNode.next=top2;
                        top2=newNode;
                    }
                }else {
                    //Insert node from left to right
                    //in first stack
                    if(temp.left!=null){
                        newNode=push(temp.left);
                        newNode.next=top1;
                        top1=newNode;
                    }
                    if(temp.right!=null){
                        newNode=push(temp.right);
                        newNode.next=top1;
                        top1=newNode;
                    }

                }


                if(currentNode==top1){
                    //when remove first stack element
                    currentNode=pop(top1);
                    top1=currentNode;
                }else{
                    //when remove second stack element
                    currentNode=pop(top2);
                    top2=currentNode;
                }

                //When currently current pointer is null, then check it which stack are not empty, 
                //if non empty stack is exist then assign this top node reference to top node of stack
                if(currentNode==null&&top1!=null) currentNode=top1; //when first stack are not empty
                else if(currentNode==null && top2!=null) currentNode=top2;//when second stack are not empty

                //Display binary tree node value
                Console.Write("  "+temp.data);
            }
        }else{
            Console.Write("Empty Linked List\n");
        }


    }
     static void Main(){
        //Make object of Binary Tree
        BinaryTree obj=new BinaryTree();

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

        //insertion of binary tree nodes
        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.right =new Node(7);
        obj.root.right.left.right =new Node(8);
        obj.root.right.right.right =new Node(9);
        //Display Node elements
        obj.spiralLevel();

    }
}

Output

  1  2  3  6  5  4  7  8  9


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