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

Linear Queue VS Circular Queue

What is Queue? A queue is one of the important linear data structures extensively used in various computer applications. It is based on the FIFO (First In First Out) principle. It...

9 minutes read.

Difference between B-tree and Binary Tree

What is B-TREE? The nodes of B-tree are sorted during in-order traversal, and it is called self-balancing tree. A node in a B-tree can have more than two offspring, in contrast...

3 minutes read.

Quick Sort

Quicksort is a sorting algorithm that uses a divide-and-conquer strategy. A pivot element is used to divide an array into subarrays (element selected from the array).  The pivot element should be...

4 minutes read.

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.

Stack vs Array

Difference between Array and Stack In this article, we are going to discuss the major differences between the stack and array data structures: Array – In the data structure, the array is...

3 minutes read.

What is a Spanning Tree in Data Structure

Data structures Data management is called database management. This allows the computer to sort or organize the data for efficient retrieval. A data model is a system used to store, manage,...

5 minutes read.

Sum of Nodes in a Binary Tree

In this article, we will see the sample problems that will help us understand the concept and summation of all the nodes in the binary tree. Implementation /* creating a program that...

4 minutes read.

What is a Sparse Matrix in Data Structure?

Definition A matrix in which a few non-zero elements are present is called a Sparse matrix. In a Sparse matrix, almost all the matrices are filled with zero (0). A matrix...

5 minutes read.

Heap Sort vs Merge Sort

In this article, we are going to discuss the Heap Sort, Merge sort and the difference between them. What is Heap Sort? Heap – A heap is an abstract data type categorised...

7 minutes read.

Top view of binary tree

We know that a binary tree is a kind of tree that helps us organize our tree and that it is a kind of non-linear info structure that at least...

4 minutes read.

Circular Linked List

Circular Linked List A circular linked list where all nodes are connected to their next node and last node is connected to the starting node or we can say all nodes...

5 minutes read.

Binary Search

Binary Search: When there is a large data structure, the linear search takes a lot of time to search the element. The binary search was developed to overcome the lack...

7 minutes read.

Operations on 2D-Arrays

Two Dimensional Array Operations Adding Elements to Two-D Arrays We must put data in both rows and columns when inserting items in 2-D Arrays. As a result, we employ the idea of...

10 minutes read.

Flatten Binary Tree to a linked list

Implementation In this section, we will see the implementation of the binary Tree and its conversion into linked lists. let us proceed: - // Writing a C++ program that will convert a...

4 minutes read.

Minimum Spanning Tree

Before getting to know about the minimum spanning tree, we should first discuss about what is a spanning tree. A spanning tree is basically a sub or minimized graph that...

7 minutes read.

Convert Sorted List to Binary Search Tree

Implementation // creating the C++ implementation of the following approach: - #include <bits/stdc++.h> using namespace std; /* Create the link list node and see its implementation. */ class L__Nod { public: int record; L__Nod* next; }; /* constructing a new binary...

15 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.

Lowest Common Ancestor in a Binary Tree

The lowest node in the tree that contains both n1 and n2 as descendants is the lowest common ancestor (LCA), and n1 and n2 are the nodes for which we...

11 minutes read.

Write Main Difference Between Tree and Graph in Data Structures

Graph: The graph has two sets, which are considered V and E. These vertices are also called nodes, and edges are referred to as arcs connecting any two nodes in a...

4 minutes read.

Applications of trees in data structures

Data structures Storage used to organize and store data is known as the data structure. It is a method of managing computerized data to translate or retrieve it more efficiently. A...

7 minutes read.