Reverse Level Order traversal in spiral form in binary tree

Reverse Level Order traversal in spiral form

Here given code implementation process.

/*
  C Program 
  Reverse Level Order traversal in spiral form in binary tree
*/
#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 in reverse level Order traversal
//In spiral form in binary tree
void reverse_spiral(struct Node*node){

    if(node !=NULL){
      //make stack pointer
      struct Stack*top1=NULL,*top2=NULL,
                  *current_node=NULL,
                  *new_node=NULL,
                  *result=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
        
        //insert node in Reverse spiral form
        new_node=push(temp);
        new_node->next=result;
        result=new_node;
      }
      while(result!=NULL){
        printf("%d  ",result->element->data);
        pop(&result);
      }
    }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
  reverse_spiral(root);
  
  return 0;


}

Output

9  8  7  4  5  6  3  2  1 
/*
  C++ Program 
+ Reverse Level Order traversal in spiral form in binary tree
*/
#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 Stack{
  public:
    Node*element;
    Stack*next;
    Stack(Node *node){
      element=node;
      next=NULL;
    }
};
class BinaryTree{
  public:
    Node*root;
    BinaryTree();
    
    Stack* push(Node*);
    Stack* pop(Stack **);
    void reverse_spiral();
};

//set initial tree root to NULL
BinaryTree:: BinaryTree(){
  root=NULL;
}
//add stack element to top
Stack* BinaryTree:: push(Node*node){
  Stack *new_node=new Stack(node);
  new_node->next=NULL;
  return new_node;
}
//remove top element of stack
Stack * BinaryTree:: pop(Stack **top){
  if(top!=NULL){
    Stack *remove=*top;
    *top=remove->next;
    remove->next=NULL;
    remove->element=NULL;
    delete remove;
    remove=NULL;
  }
  return *top;
}

//Display tree element in reverse level Order traversal
//In spiral form in binary tree
void BinaryTree:: reverse_spiral(){

    if(root !=NULL){
      //make stack pointers
      Stack*top1=NULL,
            *top2=NULL,
            *current_node=NULL,
            *new_node=NULL,
            *result=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
        
        //insert node in Reverse spiral form
        new_node=push(temp);
        new_node->next=result;
        result=new_node;
      }
      while(result!=NULL){
        cout<<"  "<<result->element->data;
        result=pop(&result);
      }
    }else{
     cout<<"Empty Linked List"<<endl;
    }
    

}
int main(){

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

  //new insert 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 Tree elements
  obj.reverse_spiral();
  return 0;
}

Output

  9  8  7  4  5  6  3  2  1
/*  
Java Program 
Reverse Level Order traversal in spiral form in binary tree
*/

//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{

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

public class BinaryTree{

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

  //add top element of stack
  public Stack push(Node node){
    Stack  new_node=new Stack(node);
   
    return new_node;
    
  }
  //remove top element of the stack
  public Stack pop(Stack top){
    if(top!=null){
      Stack  remove=top;
      top=top.next;
      remove.next=null;
      remove.element=null;

      remove=null;
    }
    return top;
  }
    //Display tree element in reverse level Order traversal
    //In spiral form in binary tree
    public void  reverse_spiral(){

    if(root !=null){
      //make stack pointers
      Stack top1=null,
             top2=null,
             current_node=null,
             new_node=null,
             result=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(temp==null) return;
        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);
          top1=current_node;
        }else{
          //when remove second stack element
          current_node=pop(top2);
          top2=current_node;
        }
        
        //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
        
        //insert node in Reverse spiral form
        new_node=push(temp);
        new_node.next=result;
        result=new_node;
      }
      while(result!=null){
       System.out.print("  "+result.element.data);
        result=pop(result);
      }
    }else{
      System.out.println("Empty Linked List");
    }
    

}

  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
    */

    //new insert 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 Tree elements
    obj.reverse_spiral();

  }
}

Output

 9  8  7  4  5  6  3  2  1
#Python Program 
#Reverse Level Order traversal in spiral form in binary tree

 
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
      self.top=None

    #remove top element of stack
    def push(self,node):
        new_node=Stack(node)
        return new_node
  
    #remove top element of the stack
    def pop(self,top):
        if(top!=None):
            remove=top
            top=top.next
            remove.next=None
            remove.element=None
            remove=None
        return top
  
    #Display tree element in reverse level Order traversal
    #In spiral form in binary tree
    def  reverse_spiral(self):

        if(self.root !=None):
            #make stack pointers
            top1=None
            current_node=None
            new_node=None
            result=None
            top2=None
            temp=self.root
            top1=self.push(temp)
            current_node=top1
            while(current_node!=None):
                #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!=None):
                        new_node=self.push(temp.right)
                        new_node.next=top2
                        top2=new_node
                    
                    if(temp.left!=None):
                        new_node=self.push(temp.left)
                        new_node.next=top2
                        top2=new_node
                    
                else :
                    #Insert node from left to right
                    #in first stack
                    if(temp.left!=None):
                        new_node=self.push(temp.left)
                        new_node.next=top1
                        top1=new_node
                    
                    if(temp.right!=None):
                        new_node=self.push(temp.right)
                        new_node.next=top1
                        top1=new_node
     
                if(current_node==top1):
                    #when remove first stack element
                    current_node=self.pop(top1)
                    top1=current_node
             
                else:
                    #when remove second stack element
                    current_node=self.pop(top2)
                    top2=current_node
                                  

                #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(current_node==None and top1!=None):
                    current_node=top1 #when first stack are not empty
                elif(current_node==None  and  top2!=None):
                    current_node=top2#when second stack are not empty

                #insert node in Reverse spiral form
                new_node=self.push(temp)
                new_node.next=result
                result=new_node
            
            while(result!=None):
                print("  ",result.element.data,end="")
                result=self.pop(result)
            
        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
    #

    #new insert 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 Tree elements
    obj.reverse_spiral();

if __name__=="__main__":
  main()

Output

   9   8   7   4   5   6   3   2   1
/* 
  C# Program 
  Reverse Level Order traversal in spiral form in binary tree
 */
using System;
class Node{

    public int data;
    public Node left, right;
    //Make a tree node
    public Node(int data){
        //Assign fields 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;

    }


    //add top element of stack
    public Stack push(Node node){
        Stack  new_node=new Stack(node);

        return new_node;

    }
    //remove top element of the stack
    public Stack pop(Stack top){
        if(top!=null){
            Stack  remove=top;
            top=top.next;
            remove.next=null;
            remove.element=null;

            remove=null;
        }
        return top;
    }
    //Display tree element in reverse level Order traversal
    //In spiral form in binary tree
    public void  reverse_spiral(){

        if(root !=null){
            //make stack pointers
            Stack top1=null,
            top2=null,
            current_node=null,
            new_node=null,
            result=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(temp==null) return;
                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);
                    top1=current_node;
                }else{
                    //when remove second stack element
                    current_node=pop(top2);
                    top2=current_node;
                }

                //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

                //insert node in Reverse spiral form
                new_node=push(temp);
                new_node.next=result;
                result=new_node;
            }
            while(result!=null){
                Console.Write("  "+result.element.data);
                result=pop(result);
            }
        }else{
            Console.WriteLine("Empty Linked List");
        }


    }
    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
    */

        //new insert 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 Tree elements
        obj.reverse_spiral();
    }
}

Output

  9  8  7  4  5  6  3  2  1

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