Logo
×

Given a Perfect Binary Tree, Reverse Alternate Levels

Implementation

//writing a program in C++ language to see how to approach it.
#include <bits/stdc++.h>
using namespace std;


// creating a tree node.
struct Nod {
	char ky;
	struct Nod *Lft, *Rt;
};


// creating a new utility function will help us establish the tree.
Nod* nw__Nod(int ky)
{
	Nod* temp = new Nod;
	temp->ky = ky;
	temp->Lft = temp->Rt = NILL;
	return (temp);
}


// Creating a new function, say utility function, that will help us in the traversal or, say, in-order traversal of the tree node. 
void inorder(Nod* root)
{
	if (root != NILL) {
		inorder(root->Lft);
		cout << root->ky << " ";
		inorder(root->Rt);
	}
}


// Now, generating a new function will help us reverse the nodes present in the tree.  
void reverseAlternate(Nod* root)
{


	// Listing the queue for the very first traversal in depth. 
	queue<Nod*> q;
	q.push(root);
	Nod* temp;


	// The level of the root we encounter at this stage is considered 1. 
	int n, level = 1;


	// the stack will store and manage all the nodes present in the tree.
	stack<int> s;


	while (!q.empty()) {
		n = q.size();
		while (n--) {
			temp = q.front();
			q.pop();


			// if the level we have is odd, then: -
			if (level % 2) {


				//We store and manage all the left and right child in the stack.
				if (temp->Lft) {
					q.push(temp->Lft);
					s.push(temp->Lft->ky);
				}


				if (temp->Rt) {
					q.push(temp->Rt);
					s.push(temp->Rt->ky);
				}
			}


			// if the level we achieve is even, then: -
			else {


// we have to simply replace the value present in the nodes with the opening of the stack. 
				temp->ky = s.top();
				s.pop();


				if (temp->Lft)
					q.push(temp->Lft);
				if (temp->Rt)
					q.push(temp->Rt);
			}
		}


		// when we increase the level:
		level++;
	}
}


// writing the main code. 
int main()
{
	struct Nod* root = nw__Nod('a');
	root->Lft = nw__Nod('b');
	root->Rt = nw__Nod('c');
	root->Lft->Lft = nw__Nod('d');
	root->Lft->Rt = nw__Nod('e');
	root->Rt->Lft = nw__Nod('f');
	root->Rt->Rt = nw__Nod('g');
	root->Lft->Lft->Lft = nw__Nod('h');
	root->Lft->Lft->Rt = nw__Nod('i');
	root->Lft->Rt->Lft = nw__Nod('j');
	root->Lft->Rt->Rt = nw__Nod('k');
	root->Rt->Lft->Lft = nw__Nod('l');
	root->Rt->Lft->Rt = nw__Nod('m');
	root->Rt->Rt->Lft = nw__Nod('n');
	root->Rt->Rt->Rt = nw__Nod('o');


	cout << "Inorder Traversal of given tree\n";
	inorder(root);


	reverseAlternate(root);


	cout << "\nInorder Traversal of modified tree\n";
	inorder(root);


	return 0;
}

Output:

Given a Perfect Binary Tree, Reverse Alternate Levels

Example 2)

//writing a program in Java language to see how to approach it.
import java.util.*;


class TFT
{
// creating a tree node.
static class Nod
{
	char ky;
	Nod Lft, Rt;
}
// creating a new utility function will help us establish the tree.
static Nod nw__Nod(char ky)
{
	Nod temp = new Nod();
	temp.ky = ky;
	temp.Lft = temp.Rt = NILL;
	return (temp);
}
// Creating a new function, say utility function, will help us in the traversal or in-order traversal of the tree node. 
static void inorder(Nod root)
{
	if (root != NILL)
	{
		inorder(root.Lft);
		System.out.print(root.ky + " ");
		inorder(root.Rt);
	}
}
// Now, generating a new function will help us reverse the nodes present in the tree.  
static void reverseAlternate(Nod root)
{
// Listing the queue for the very first traversal in depth.
	Queue<Nod> q = new LinkedList<Nod> ();
	q.add(root);
	Nod temp;
	// The level of the root we encounter at this stage is considered 1. 
	int n, level = 1;
	// the stack will store and manage all the nodes present in the tree.
	Stack<Character> s = new Stack<Character> ();
	while (!q.isEmpty())
	{
		n = q.size();
		while (n != 0)
		{
			if(!q.isEmpty())
			{
				temp = q.peek();
				q.remove();
			}
			else
			temp = NILL;
	// if the level we have is odd, then: -
	if (level % 2 != 0)
			{


		//We store and manage all the left and right child in the stack.
				if (temp != NILL && temp.Lft != NILL)
				{
					q.add(temp.Lft);
					s.push(temp.Lft.ky);
				}


				if (temp != NILL && temp.Rt != NILL)
				{
					q.add(temp.Rt);
					s.push(temp.Rt.ky);
				}
			}


	// if the level we achieve is even, then: -
			else
			{
// we have to simply replace the value present in the nodes with the opening of the stack.
				temp.ky = s.peek();
				s.pop();


				if (temp.Lft != NILL)
					q.add(temp.Lft);
				if (temp.Rt != NILL)
					q.add(temp.Rt);
			}
			n--;
		}


			// when we increase the level:
		level++;
	}
}
// writing the main code. 
public static void main(String[] args)
{
	Nod root = nw__Nod('a');
	root.Lft = nw__Nod('b');
	root.Rt = nw__Nod('c');
	root.Lft.Lft = nw__Nod('d');
	root.Lft.Rt = nw__Nod('e');
	root.Rt.Lft = nw__Nod('f');
	root.Rt.Rt = nw__Nod('g');
	root.Lft.Lft.Lft = nw__Nod('h');
	root.Lft.Lft.Rt = nw__Nod('i');
	root.Lft.Rt.Lft = nw__Nod('j');
	root.Lft.Rt.Rt = nw__Nod('k');
	root.Rt.Lft.Lft = nw__Nod('l');
	root.Rt.Lft.Rt = nw__Nod('m');
	root.Rt.Rt.Lft = nw__Nod('n');
	root.Rt.Rt.Rt = nw__Nod('o');


	System.out.println("Inorder Traversal of given tree");
	inorder(root);


	reverseAlternate(root);


	System.out.println("\nInorder Traversal of modified tree");
	inorder(root);
}
}

Output:

Given a Perfect Binary Tree, Reverse Alternate Levels

Example 3)

# writing a program in python language to see how to approach it.
# creating a tree node.
class Nod:
	
	def __init__(self, ky):
	
		self.ky = ky
		self.Lft = None
		self.Rt = None
	
# creating a new utility function that will help us establish the tree.
def nw__Nod(ky):


	temp = Nod(ky)
	return temp


# Creating a new function, say utility function, that will help us in the traversal or, say, in-order traversal of the tree node. 
def inorder(root):


	if (root != None):
		inorder(root.Lft);
		print(root.ky,
			end = ' ')
		inorder(root.Rt);


# Now, generating a new function will help us reverse the nodes present in the tree.  
def reverse alternate(root):


	# Listing the queue for the very first traversal in depth.
	q = []
	q.append(root);
	
	temp = None


	# The level of the root which we encounter at this stage is to be considered as 1. 
	n = 0
	level = 1;


	# the stack will store and manage all the nodes present in the tree.
	s = []


	while (len(q) != 0):	
		n = len(q);	
		while (n != 0):		
			n -= 1
			temp = q[0];
			q.pop(0);


			# if the level we have is odd, then: -
			if (level % 2 != 0):
	# We store and manage all the left and right child in the stack.
				if (temp.Lft != None):
					q.append(temp.Lft);
					s.append(temp.Lft.ky);
				


				if (temp.Rt != None):
					q.append(temp.Rt);
					s.append(temp.Rt.ky);


			# if the level we achieve is even, then: -
			else:


	# we have to replace the value present in the nodes with the opening of the stack.
				temp.ky = s[-1];
				s.pop();


				if (temp.Lft != None):
					q.append(temp.Lft);
				if (temp.Rt != None):
					q.append(temp.Rt);


		# when we increase the level:
		level += 1;


# writing the main code. 
if __name__ == "__main__":
	
	root = nw__Nod('a');
	root.Lft = nw__Nod('b');
	root.Rt = nw__Nod('c');
	root.Lft.Lft = nw__Nod('d');
	root.Lft.Rt = nw__Nod('e');
	root.Rt.Lft = nw__Nod('f');
	root.Rt.Rt = nw__Nod('g');
	root.Lft.Lft.Lft = nw__Nod('h');
	root.Lft.Lft.Rt = nw__Nod('i');
	root.Lft.Rt.Lft = nw__Nod('j');
	root.Lft.Rt.Rt = nw__Nod('k');
	root.Rt.Lft.Lft = nw__Nod('l');
	root.Rt.Lft.Rt = nw__Nod('m');
	root.Rt.Rt.Lft = nw__Nod('n');
	root.Rt.Rt.Rt = nw__Nod('o');
	
	print("Inorder Traversal of given tree")
	inorder(root);


	reverseAlternate(root);
	
	print("\nInorder Traversal of modified tree")
	inorder(root);

Output:

Given a Perfect Binary Tree, Reverse Alternate Levels

Example 4)

// writing a program in CPP language to see how to approach it.
using System;
using System. Collections;


class TFT
{
// creating a tree node.
public class Nod
{
	public char ky;
	public Nod Lft, Rt;
}
// creating a new utility function will help us establish the tree.
static Nod nw__Nod(char ky)
{
	Nod temp = new Nod();
	temp.ky = ky;
	temp.Lft = temp.Rt = NILL;
	return (temp);
}
// Creating a new function, say utility function, will help us in the traversal or in-order traversal of the tree node. 
static void inorder(Nod root)
{
	if (root != NILL)
	{
		inorder(root.Lft);
		Console.Write(root.ky + " ");
		inorder(root.Rt);
	}
}
// Now, generating a new function will help us reverse the nodes present in the tree.  
static void reverseAlternate(Nod root)
{
// Listing the queue for the very first traversal in depth.
	Queue q = new Queue ();
	q.Enqueue(root);
	Nod temp;
	// The level of the root we encounter at this stage is considered 1. 
	int n, level = 1;
	// the stack will store and manage all the nodes present in the tree.
	Stack s = new Stack ();


	while (q.Count > 0)
	{
		n = q.Count;
		while (n != 0)
		{
			if(q.Count > 0)
			{
				temp = (Nod)q.Peek();
				q.Dequeue();
			}
			else
			temp = NILL;
	// if the level we have is odd, then: -	
	if (level % 2 != 0)
			{


	//We store and manage all the left and right child in the stack.
				if (temp != NILL && temp.Lft != NILL)
				{
					q.Enqueue(temp.Lft);
					s.Push(temp.Lft.ky);
				}


				if (temp != NILL && temp.Rt != NILL)
				{
					q.Enqueue(temp.Rt);
					s.Push(temp.Rt.ky);
				}
			}


	// if the level we achieve is even, then: -
			else
			{
// we have to simply replace the value present in the nodes with the opening of the stack.
				temp.ky =(char)s.Peek();
				s.Pop();


				if (temp.Lft != NILL)
					q.Enqueue(temp.Lft);
				if (temp.Rt != NILL)
					q.Enqueue(temp.Rt);
			}
			n--;
		}


			// when we increase the level:
		level++;
	}
}
// writing the main code. 
public static void Main(String []args)
{
	Nod root = nw__Nod('a');
	root.Lft = nw__Nod('b');
	root.Rt = nw__Nod('c');
	root.Lft.Lft = nw__Nod('d');
	root.Lft.Rt = nw__Nod('e');
	root.Rt.Lft = nw__Nod('f');
	root.Rt.Rt = nw__Nod('g');
	root.Lft.Lft.Lft = nw__Nod('h');
	root.Lft.Lft.Rt = nw__Nod('i');
	root.Lft.Rt.Lft = nw__Nod('j');
	root.Lft.Rt.Rt = nw__Nod('k');
	root.Rt.Lft.Lft = nw__Nod('l');
	root.Rt.Lft.Rt = nw__Nod('m');
	root.Rt.Rt.Lft = nw__Nod('n');
	root.Rt.Rt.Rt = nw__Nod('o');


	Console.WriteLine("Inorder Traversal of given tree");
	inorder(root);


	reverseAlternate(root);


	Console.WriteLine("\nInorder Traversal of modified tree");
	inorder(root);
}
}

Output:

Given a Perfect Binary Tree, Reverse Alternate Levels

Example 5)

<script>
//writing a program in Javascript language to see how to approach it.
// creating a tree node.
class Nod
{
	constructor()
	{
		this.ky = '';
		this.Lft = NILL;
		this.Rt = NILL;
	}
}


// creating a new utility function will help us establish the tree.
function nw__Nod(ky)
{
	var temp = new Nod();
	temp.ky = ky;
	temp.Lft = temp.Rt = NILL;
	return (temp);
}
// Creating a new function, say utility function, will help us in the traversal or in-order traversal of the tree node. 
function inorder(root)
{
	if (root != NILL)
	{
		inorder(root.Lft);
		document.write(root.ky + " ");
		inorder(root.Rt);
	}
}
// Now, generating a new function will help us reverse the nodes present in the tree.  
function reverseAlternate(root)
{
// Listing the queue for the very first traversal in depth.
	var q = [];
	q.push(root);
	var temp = NILL;
	// The level of the root we encounter at this stage is considered 1. 


	var n, level = 1;


	// the stack will store and manage all the nodes present in the tree.
	var s = [];


	while (q.length > 0)
	{
		n = q.length;
		while (n != 0)
		{
			if(q.length > 0)
			{
				temp = q[0];
				q.shift();
			}
			else
			temp = NILL;
// if the level we have is odd, then: -	
			if (level % 2 != 0)
			{
	//We store and manage all the left and right child in the stack.
				if (temp != NILL && temp.Lft != NILL)
				{
					q.push(temp.Lft);
					s.push(temp.Lft.ky);
				}


				if (temp != NILL && temp.Rt != NILL)
				{
					q.push(temp.Rt);
					s.push(temp.Rt.ky);
				}
			}
// if the level we achieve is even, then: -
			else
			{
// we have to simply replace the value present in the nodes with the opening of the stack. 
				temp.ky = s[s.length-1];
				s.pop();


				if (temp.Lft != NILL)
					q.push(temp.Lft);
				if (temp.Rt != NILL)
					q.push(temp.Rt);
			}
			n--;
		}
	// when we increase the level:
		level++;
	}
}
// writing the main code. 
var root = nw__Nod('a');
root.Lft = nw__Nod('b');
root.Rt = nw__Nod('c');
root.Lft.Lft = nw__Nod('d');
root.Lft.Rt = nw__Nod('e');
root.Rt.Lft = nw__Nod('f');
root.Rt.Rt = nw__Nod('g');
root.Lft.Lft.Lft = nw__Nod('h');
root.Lft.Lft.Rt = nw__Nod('i');
root.Lft.Rt.Lft = nw__Nod('j');
root.Lft.Rt.Rt = nw__Nod('k');
root.Rt.Lft.Lft = nw__Nod('l');
root.Rt.Lft.Rt = nw__Nod('m');
root.Rt.Rt.Lft = nw__Nod('n');
root.Rt.Rt.Rt = nw__Nod('o');
document.write("Inorder Traversal of given tree<br>");
inorder(root);
reverseAlternate(root);
document.write("<br>Inorder Traversal of modified tree<br>");
inorder(root);


</script>

Output:

Given a Perfect Binary Tree, Reverse Alternate Levels

Related Topics

Find the nth node from the end of a Linked List

Find the nth node from the end of a Linked List In this problem, we have given a singly linked list and a number 'n,' and we need to find the...

3 minutes read.

Recaman’s Sequence

Recamán's succession repeat connection in arithmetic and software engineering. Since its components are obviously connected with the past components, they are as often as possible characterized utilizing recursion. It takes its...

4 minutes read.

Cycle sort

Cycle sort is an examination arranging calculation which powers exhibit to be figured into the quantity of cycles where every one of them can be pivoted to create an arranged...

5 minutes read.

Tree vs Graph: Data Structure

Difference Between Tree and Graph What is Tree? A tree is a non-linear data structure and finite collection of elements called node. A tree, in which the data items are arranged in...

3 minutes read.

Asymptotic Notation

Asymptotic notation is expressions that are used to represent the complexity of algorithms. The complexity of the algorithm is analyzed from two perspectives:  Time complexitySpace complexity Time complexity The time complexity of an algorithm is the...

3 minutes read.

Stack Using Linked List

In the linked list implementation of the stack, we use a linked list as the primitive data structure to create the stack. It is called the dynamic implementation of the...

6 minutes read.

Insertion Sort in Data Structures

Insertion Sort in C++ Insertion sort is a sorting algorithm that, in each iteration, installs an unsorted element in its proper position Insertion sort operates in a similar way to how we...

3 minutes read.

Serialize and Deserialize a Binary Tree

Implementation // Writing a C++ program to check the serialization and deserialization of binary tree.   #include <iosstream> /* A binary tree node contains a key and a pointer to the left and right...

4 minutes read.

Find Number of Minimum Insertion to Make a String Palindrome

You have been given a string. You have to find out the number of minimum insertions to make this string palindrome. The string will contain only lower case alphabets. Note:What is...

4 minutes read.

Sorting Algorithms in Data Structures

A sorting algorithm is used to organize the elements of an array or list. Sorting an array, for example. Unsorted array 572941 Sorted array 124579 We're sorting the array in ascending order right now. This procedure...

4 minutes read.

How to Start Learning DSA

All programmer experiences a point along the way where they wish they could approach a problem in a more effective manner. They finally learn about the terminology DSA while trying...

10 minutes read.

Binary Tree Inorder Traversal

The binary tree is a type of tree in which each and every node has atleast two children except the leaf nodes. We have various operations in the binary tree,...

4 minutes read.

What is an AVL Tree in Data Structure?

AVL tree stands for (Adelson, Velskii, & Landis Tree) Data structure Data management is called database management. A data model is a system used to store, manage, and optimize computer resources. Data...

4 minutes read.

Program to calculate the area of the circumcircle of an equilateral triangle

You have given one value which represents the side of the equilateral triangle. You have to find out the area of the circumcircle. Let’s take an example - For the above...

3 minutes read.

What is a full Binary Tree?

A full binary tree is considered to be a special kind of binary tree in which every single node or leaf node present either contains two children or no children...

4 minutes read.

Threaded Binary Trees

Introduction Threaded Binary Trees (TBTs) are an enhancement of normal binary trees intended for in-order traversal only. This means that this data structure is developed with the objective of making the...

12 minutes read.

Given a Binary Tree Return All Root-to-Leaf Paths

Implementation #include <bits/stdc++.h> using namespace std; // A binary tree node generally consists of data, a pointer to the left and right child, and a pointer to the right child.  class __nod { public: int record; __nod* Lft; __nod*...

9 minutes read.

Understanding Data Processing

Introduction Data In our everyday lives, any task that we perform online is related to data. Millions of pieces of data are produced every second across the globe. Data production is largely...

4 minutes read.

Check if a Singly Linked List is Palindrome

Check if a Singly Linked List is Palindrome In this section, we have given a singly linked list, and we need to check whether the given list is a palindrome. Example:           1...

3 minutes read.

Deletion Operation of the binary search tree in C++ language

A typical binary search tree implements some order to carry out the arrangements. As the name suggests, each parent node should have at most two children. The main rule in...

4 minutes read.