Reverse Level Order traversal in spiral form in binary tree
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