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:

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:

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:

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:

Data Structures Tutorial

Misc Topic:

Data Structures Tutorial

Misc Topic:

Given a Perfect Binary Tree, Reverse Alternate Levels

Implementation