Posted on by Kalkicode
Code Queue

# Reverse alternate levels of a binary tree

The problem involves reversing alternate levels of a binary tree and then printing the nodes of the reversed tree level by level. In other words, nodes at even levels will be reversed, and nodes at odd levels will remain unchanged.

## Problem Statement

Given a binary tree, the task is to reverse alternate levels of the tree and then print the nodes of the reversed tree level by level.

## Example Scenario

Consider the binary tree shown below:

7
/   \
3     4
/     / \
2     6   8
/  \     \   \
1    5     7  10
/ \     \
9   3     11

After reversing alternate levels, the tree becomes:

7
/   \
4     3
/     / \
2     6   8
/  \     \   \
10   7     5   1
/ \     \
11   3    9

The levels are then printed level by level:

• Level 1: 7
• Level 2: 4 3
• Level 3: 2 6 8
• Level 4: 10 7 5 1
• Level 5: 11 3 9

## Idea to Solve the Problem

To solve this problem, we can perform a level-order traversal of the tree and reverse the nodes' values in alternate levels while storing them in a queue. Then, print the queue in the same level-order manner.

## Pseudocode

void reverse_alternate_level(struct Node *root)
{
// Check if the root is NULL
if (root == NULL)
{
printf("Empty Tree\n");
return;
}

// Initialize a queue
// Enqueue the root node with level 1
// Initialize level

while (queue is not empty)
{
// Traverse the current level

// Reverse alternate levels' nodes
// Change values of nodes in alternate levels

// Print the nodes' values for the current level

// Dequeue nodes from the queue
}
}

## Algorithm Explanation

1. Implement the reverse_alternate_level function that takes the root of the binary tree as input.
2. Check if the root is NULL, if so, print "Empty Tree" and return.
3. Initialize a queue data structure for the BFS traversal.
4. Enqueue the root node along with its level (starting from 1).
5. Start a loop that continues until the queue is empty.
6. Inside the loop, traverse the current level and reverse the nodes' values in alternate levels.
7. Print the nodes' values for the current level.
8. Dequeue nodes from the queue as you process them.
9. This process ensures that all levels are traversed, nodes' values are reversed in alternate levels, and the nodes' values are printed.

## Code Solution

// C program
// Reverse alternate levels of a binary tree
#include <stdio.h>
#include <stdlib.h>

//Node of binary tree
struct Node
{
int data;
struct Node *left, *right;
};
struct MyQueue
{
int level;
struct Node *element;
struct MyQueue *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 node value
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
printf("Memory Overflow\n");
}
//return reference
return new_node;
}
//Create a queue node and returns this node
struct MyQueue *enqueue(struct Node *tree_node)
{
//Make a new Queue node
struct MyQueue *new_node = (struct MyQueue *) malloc(sizeof(struct MyQueue));
if (new_node != NULL)
{
//Set node values
new_node->element = tree_node;
new_node->next = NULL;
}
else
{
printf("Memory Overflow\n");
}
return new_node;
}
//Remove a queue elements
void dequeue(struct MyQueue **front)
{
if ( *front != NULL)
{
struct MyQueue *remove = *front;
//Visit to next node
*front = remove->next;
remove->element = NULL;
remove->next = NULL;
//free node
free(remove);
remove = NULL;
}
}
//Reverse level nodes
void reverse_level(struct MyQueue *front, int level)
{
if (front == NULL)
{
return;
}
int size = 0;
struct MyQueue *temp = front;
//Count number of nodes in given level
while (temp != NULL && temp->level == level)
{
size++;
temp = temp->next;
}
if (size == 1)
{
//When only one element in given level
return;
}
else
{
//Useful for storing level values
int collection[size];
int location = 0;
//Start to first node
temp = front;
//Get level nodes from left to right
while (temp != NULL && temp->level == level)
{
// Get node value
collection[location] = temp->element->data;
temp = temp->next;
// Change location
location++;
}
location = size - 1;
//Start to first node
temp = front;
// Update level node with its reverse order node value
while (location >= 0 && temp != NULL && temp->level == level)
{
temp->element->data = collection[location];
temp = temp->next;
location--;
}
}
}
// Travers the level order nodes in binary tree and
// Display alternate reversal level nodes
void reverse_alternate_level(struct Node *root)
{
if (root != NULL)
{
//make queue pointers
struct MyQueue *front = NULL, *tail = NULL;
struct MyQueue *temp = NULL;
//make a tree pointer
struct Node *node = NULL;
//Get first node of tree
front = enqueue(root);
//Start level of first node is one
front->level = 1;
//Set tail node to first node
tail = front;
// Start to first node
temp = front;
int level = 0;
// Get level elements into a queue
while (temp != NULL)
{
//Tree node
node = temp->element;
//Get node level
level = temp->level + 1;
if (node->left != NULL)
{
tail->next = enqueue(node->left);
tail->next->level = level;
tail = tail->next;
}
if (node->right != NULL)
{
tail->next = enqueue(node->right);
tail->next->level = level;
tail = tail->next;
}
//Visit to next node queue
temp = temp->next;
}
//Print level nodes, and reverse alternate level elements
while (front != NULL)
{
// Get node level
level = front->level;
printf(" [");
if (level % 2 == 0)
{
//This reverse level
reverse_level(front, level);
}
//Print and removing queue nodes
while (front != NULL && front->level == level)
{
printf(" %d ", front->element->data);
//remove  a queue node
dequeue( &front);
}
printf("]\n");
}
tail = NULL;
}
else
{
printf("Empty Tree\n");
}
}
int main()
{
struct Node *root = NULL;
/*
Construct Binary Tree
-----------------------
7
/    \
/      \
3        4
/      /    \
2      6      8
/  \     \    /
1    5     7  10
/ \     \
9   3     11
-- -- -- -- -- -- -- -- -- -- -- -
*/
root = insert(7);
root->left = insert(3);
root->right = insert(4);
root->right->right = insert(8);
root->right->left = insert(6);
root->left->left = insert(2);
root->left->left->left = insert(1);
root->left->left->right = insert(5);
root->right->left->right = insert(7);
root->right->right->left = insert(10);
root->left->left->right->left = insert(9);
root->left->left->right->right = insert(3);
root->right->left->right->right = insert(11);
/*
Converted Binary tree
-----------------------
7
/    \
/      \
4        3   // change level
/      /    \
2      6      8
/  \     \    /
10   7     5  1   // change level
/ \     \
9   3     11
-- -- -- -- -- -- -- -- -- -- -- - */
reverse_alternate_level(root);
return 0;
}

#### Output

[ 7 ]
[ 4  3 ]
[ 2  6  8 ]
[ 10  7  5  1 ]
[ 9  3  11 ]
/*
Java program
Reverse alternate levels of a binary tree
*/
//Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public int level;
public QueueNode(TreeNode element, int level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element, int level)
{
QueueNode new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
public boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
//Reverse level nodes
public void reverse_level(MyQueue queue, int level)
{
if (queue.front == null)
{
return;
}
int size = 0;
QueueNode temp = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
size++;
temp = temp.next;
}
if (size == 1)
{
//When only one element in given level
return;
}
else
{
//Useful for storing level values
int[] collection = new int[size];
int location = 0;
//Start to first node
temp = queue.front;
//Get level nodes from left to right
while (temp != null && temp.level == level)
{
// Get node value
collection[location] = temp.element.data;
temp = temp.next;
// Change location
location++;
}
location = size - 1;
//Start to first node
temp = queue.front;
// Update level node with its reverse order node value
while (location >= 0 && temp != null && temp.level == level)
{
temp.element.data = collection[location];
temp = temp.next;
location--;
}
}
}
// Travers the level order nodes in binary tree and
// Display alternate reversal level nodes
public void reverse_alternate_level()
{
if (this.root == null)
{
System.out.print("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
TreeNode node = this.root;
//Create a Queue
MyQueue queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
QueueNode temp = queue.front;
int level = 0;
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
level = 0;
//Print level nodes, and reverse alternate level elements
while (queue.is_empty() == false)
{
level = queue.front.level;
System.out.print(" [");
if (level % 2 == 0)
{
//This reverse level
reverse_level(queue, level);
}
//Print and removing queue nodes
while (queue.is_empty() == false && queue.front.level == level)
{
//When sum exist
System.out.print(" " + queue.front.element.data);
//remove  a queue node
queue.dequeue();
}
System.out.print(" ]\n");
}
}
}
public static void main(String[] args)
{
//Object of Binary Tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
7
/    \
/      \
3        4
/      /    \
2      6      8
/  \     \    /
1    5     7  10
/ \     \
9   3     11
--------------------------
*/
tree.root = new TreeNode(7);
tree.root.left = new TreeNode(3);
tree.root.right = new TreeNode(4);
tree.root.right.right = new TreeNode(8);
tree.root.right.left = new TreeNode(6);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(1);
tree.root.left.left.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(10);
tree.root.left.left.right.left = new TreeNode(9);
tree.root.left.left.right.right = new TreeNode(3);
tree.root.right.left.right.right = new TreeNode(11);
/*
Converted Binary tree
-----------------------
7
/    \
/      \
4        3   // change level
/      /    \
2      6      8
/  \     \    /
10   7     5  1   // change level
/ \     \
9   3     11
-----------------------
*/
tree.reverse_alternate_level();
}
}

#### Output

[ 7 ]
[ 4 3 ]
[ 2 6 8 ]
[ 10 7 5 1 ]
[ 9 3 11 ]
#include <iostream>

using namespace std;
/*
C++ program
Reverse alternate levels of a binary tree
*/
//Binary Tree node
class TreeNode
{
public: int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
//set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Queue Node
class QueueNode
{
public: TreeNode *element;
QueueNode *next;
int level;
QueueNode(TreeNode *element, int level)
{
this->element = element;
this->next = NULL;
this->level = level;
}
};
//Define custom queue class
class MyQueue
{
public: QueueNode *front;
QueueNode *tail;
MyQueue()
{
this->front = NULL;
this->tail = NULL;
}
//Add a new node at last of queue
void enqueue(TreeNode *element, int level)
{
QueueNode *new_node = new QueueNode(element, level);
if (this->front == NULL)
{
//When first node of queue
this->front = new_node;
}
else
{
this->tail->next = new_node;
}
this->tail = new_node;
}
//Delete first node of queue
void dequeue()
{
if (this->front != NULL)
{
if (this->tail == this->front)
{
this->tail = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
}
}
}
bool is_empty()
{
if (this->front == NULL)
{
return true;
}
else
{
return false;
}
}
};
class BinaryTree
{
public: TreeNode *root;
BinaryTree()
{
// Set initial tree root to null
this->root = NULL;
}
//Reverse level nodes
void reverse_level(MyQueue queue, int level)
{
if (queue.front == NULL)
{
return;
}
int size = 0;
QueueNode *temp = queue.front;
//Count number of nodes in given level
while (temp != NULL && temp->level == level)
{
size++;
temp = temp->next;
}
if (size == 1)
{
//When only one element in given level
return;
}
else
{
//Useful for storing level values
int collection[size];
int location = 0;
//Start to first node
temp = queue.front;
//Get level nodes from left to right
while (temp != NULL && temp->level == level)
{
// Get node value
collection[location] = temp->element->data;
temp = temp->next;
// Change location
location++;
}
location = size - 1;
//Start to first node
temp = queue.front;
// Update level node with its reverse order node value
while (location >= 0 && temp != NULL && temp->level == level)
{
temp->element->data = collection[location];
temp = temp->next;
location--;
}
}
}
// Travers the level order nodes in binary tree and
// Display alternate reversal level nodes
void reverse_alternate_level()
{
if (this->root == NULL)
{
cout << "\n Empty Binary Tree \n";
}
else
{
//Get top node in tree
TreeNode *node = this->root;
//Create a Queue
MyQueue queue = MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
QueueNode *temp = queue.front;
int level = 0;
while (temp != NULL)
{
node = temp->element;
level = temp->level;
if (node->left != NULL)
{
queue.enqueue(node->left, level + 1);
}
if (node->right != NULL)
{
queue.enqueue(node->right, level + 1);
}
temp = temp->next;
}
level = 0;
//Print level nodes, and reverse alternate level elements
while (queue.is_empty() == false)
{
level = queue.front->level;
cout << " [";
if (level % 2 == 0)
{
//This reverse level
this->reverse_level(queue, level);
}
//Print and removing queue nodes
while (queue.is_empty() == false && queue.front->level == level)
{
//When sum exist
cout << " " << queue.front->element->data;
//remove  a queue node
queue.dequeue();
}
cout << " ]\n";
}
}
}
};
int main()
{
//Object of Binary Tree
BinaryTree tree = BinaryTree();
/*
Construct Binary Tree
-----------------------
7
/    \
/      \
3        4
/      /    \
2      6      8
/  \     \    /
1    5     7  10
/ \     \
9   3     11
--------------------------
*/

tree.root = new TreeNode(7);
tree.root->left = new TreeNode(3);
tree.root->right = new TreeNode(4);
tree.root->right->right = new TreeNode(8);
tree.root->right->left = new TreeNode(6);
tree.root->left->left = new TreeNode(2);
tree.root->left->left->left = new TreeNode(1);
tree.root->left->left->right = new TreeNode(5);
tree.root->right->left->right = new TreeNode(7);
tree.root->right->right->left = new TreeNode(10);
tree.root->left->left->right->left = new TreeNode(9);
tree.root->left->left->right->right = new TreeNode(3);
tree.root->right->left->right->right = new TreeNode(11);
/*
Converted Binary tree
-----------------------
7
/    \
/      \
4        3   // change level
/      /    \
2      6      8
/  \     \    /
10   7     5  1   // change level
/ \     \
9   3     11
-----------------------
*/
tree.reverse_alternate_level();
return 0;
}

#### Output

[ 7 ]
[ 4 3 ]
[ 2 6 8 ]
[ 10 7 5 1 ]
[ 9 3 11 ]
//Include namespace system
using System;
/*
C# program
Reverse alternate levels of a binary tree
*/
//Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
public TreeNode element;
public QueueNode next;
public int level;
public QueueNode(TreeNode element, int level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
public QueueNode front;
public QueueNode tail;
public MyQueue()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
public void enqueue(TreeNode element, int level)
{
QueueNode new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
public void dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
public Boolean is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
// Set initial tree root to null
this.root = null;
}
//Reverse level nodes
public void reverse_level(MyQueue queue, int level)
{
if (queue.front == null)
{
return;
}
int size = 0;
QueueNode temp = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
size++;
temp = temp.next;
}
if (size == 1)
{
//When only one element in given level
return;
}
else
{
//Useful for storing level values
int[] collection = new int[size];
int location = 0;
//Start to first node
temp = queue.front;
//Get level nodes from left to right
while (temp != null && temp.level == level)
{
// Get node value
collection[location] = temp.element.data;
temp = temp.next;
// Change location
location++;
}
location = size - 1;
//Start to first node
temp = queue.front;
// Update level node with its reverse order node value
while (location >= 0 && temp != null && temp.level == level)
{
temp.element.data = collection[location];
temp = temp.next;
location--;
}
}
}
// Travers the level order nodes in binary tree and
// Display alternate reversal level nodes
public void reverse_alternate_level()
{
if (this.root == null)
{
Console.Write("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
TreeNode node = this.root;
//Create a Queue
MyQueue queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
QueueNode temp = queue.front;
int level = 0;
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
level = 0;
//Print level nodes, and reverse alternate level elements
while (queue.is_empty() == false)
{
level = queue.front.level;
Console.Write(" [");
if (level % 2 == 0)
{
//This reverse level
reverse_level(queue, level);
}
//Print and removing queue nodes
while (queue.is_empty() == false && queue.front.level == level)
{
//When sum exist
Console.Write(" " + queue.front.element.data);
//remove  a queue node
queue.dequeue();
}
Console.Write(" ]\n");
}
}
}
public static void Main(String[] args)
{
//Object of Binary Tree
BinaryTree tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
7
/    \
/      \
3        4
/      /    \
2      6      8
/  \     \    /
1    5     7  10
/ \     \
9   3     11
--------------------------
*/

tree.root = new TreeNode(7);
tree.root.left = new TreeNode(3);
tree.root.right = new TreeNode(4);
tree.root.right.right = new TreeNode(8);
tree.root.right.left = new TreeNode(6);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(1);
tree.root.left.left.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(10);
tree.root.left.left.right.left = new TreeNode(9);
tree.root.left.left.right.right = new TreeNode(3);
tree.root.right.left.right.right = new TreeNode(11);
/*
Converted Binary tree
-----------------------
7
/    \
/      \
4        3   // change level
/      /    \
2      6      8
/  \     \    /
10   7     5  1   // change level
/ \     \
9   3     11
-----------------------
*/
tree.reverse_alternate_level();
}
}

#### Output

[ 7 ]
[ 4 3 ]
[ 2 6 8 ]
[ 10 7 5 1 ]
[ 9 3 11 ]
<?php
/*
Php program
Reverse alternate levels of a binary tree
*/

//Binary Tree node
class TreeNode
{
public \$data;
public \$left;
public \$right;

function __construct(\$data)
{
//set node value
\$this->data = \$data;
\$this->left = null;
\$this->right = null;
}
}
// Queue Node
class QueueNode
{
public \$element;
public \$next;
public \$level;

function __construct(\$element, \$level)
{
\$this->element = \$element;
\$this->next = null;
\$this->level = \$level;
}
}
//Define custom queue class
class MyQueue
{
public \$front;
public \$tail;

function __construct()
{
\$this->front = null;
\$this->tail = null;
}
//Add a new node at last of queue
public	function enqueue(\$element, \$level)
{
\$new_node = new QueueNode(\$element, \$level);
if (\$this->front == null)
{
//When first node of queue
\$this->front = \$new_node;
}
else
{
\$this->tail->next = \$new_node;
}
\$this->tail = \$new_node;
}
//Delete first node of queue
public	function dequeue()
{
if (\$this->front != null)
{
if (\$this->tail == \$this->front)
{
\$this->tail = null;
\$this->front = null;
}
else
{
\$this->front = \$this->front->next;
}
}
}
public	function is_empty()
{
if (\$this->front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
public \$root;

function __construct()
{
// Set initial tree root to null
\$this->root = null;
}
//Reverse level nodes
public	function reverse_level(\$queue, \$level)
{
if (\$queue->front == null)
{
return;
}
\$size = 0;
\$temp = \$queue->front;
//Count number of nodes in given level
while (\$temp != null && \$temp->level == \$level)
{
\$size++;
\$temp = \$temp->next;
}
if (\$size == 1)
{
//When only one element in given level
return;
}
else
{
//Useful for storing level values
\$collection = array_fill(0, \$size, 0);
\$location = 0;
//Start to first node
\$temp = \$queue->front;
//Get level nodes from left to right
while (\$temp != null && \$temp->level == \$level)
{
// Get node value
\$collection[\$location] = \$temp->element->data;
\$temp = \$temp->next;
// Change location
\$location++;
}
\$location = \$size - 1;
//Start to first node
\$temp = \$queue->front;
// Update level node with its reverse order node value
while (\$location >= 0 && \$temp != null && \$temp->level == \$level)
{
\$temp->element->data = \$collection[\$location];
\$temp = \$temp->next;
\$location--;
}
}
}
// Travers the level order nodes in binary tree and
// Display alternate reversal level nodes
public	function reverse_alternate_level()
{
if (\$this->root == null)
{
echo "\n Empty Binary Tree \n";
}
else
{
//Get top node in tree
\$node = \$this->root;
//Create a Queue
\$queue = new MyQueue();
//Add first node at the level of one
\$queue->enqueue(\$node, 1);
\$temp = \$queue->front;
\$level = 0;
while (\$temp != null)
{
\$node = \$temp->element;
\$level = \$temp->level;
if (\$node->left != null)
{
\$queue->enqueue(\$node->left, \$level + 1);
}
if (\$node->right != null)
{
\$queue->enqueue(\$node->right, \$level + 1);
}
\$temp = \$temp->next;
}
\$level = 0;
//Print level nodes, and reverse alternate level elements
while (\$queue->is_empty() == false)
{
\$level = \$queue->front->level;
echo " [";
if (\$level % 2 == 0)
{
//This reverse level
\$this->reverse_level(\$queue, \$level);
}
//Print and removing queue nodes
while (\$queue->is_empty() == false && \$queue->front->level == \$level)
{
//When sum exist
echo " ". \$queue->front->element->data;
//remove  a queue node
\$queue->dequeue();
}
echo " ]\n";
}
}
}
}

function main()
{
//Object of Binary Tree
\$tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
7
/    \
/      \
3        4
/      /    \
2      6      8
/  \     \    /
1    5     7  10
/ \     \
9   3     11
--------------------------
*/

\$tree->root = new TreeNode(7);
\$tree->root->left = new TreeNode(3);
\$tree->root->right = new TreeNode(4);
\$tree->root->right->right = new TreeNode(8);
\$tree->root->right->left = new TreeNode(6);
\$tree->root->left->left = new TreeNode(2);
\$tree->root->left->left->left = new TreeNode(1);
\$tree->root->left->left->right = new TreeNode(5);
\$tree->root->right->left->right = new TreeNode(7);
\$tree->root->right->right->left = new TreeNode(10);
\$tree->root->left->left->right->left = new TreeNode(9);
\$tree->root->left->left->right->right = new TreeNode(3);
\$tree->root->right->left->right->right = new TreeNode(11);
/*
Converted Binary tree
-----------------------
7
/    \
/      \
4        3   // change level
/      /    \
2      6      8
/  \     \    /
10   7     5  1   // change level
/ \     \
9   3     11
-----------------------
*/
\$tree->reverse_alternate_level();
}
main();

#### Output

[ 7 ]
[ 4 3 ]
[ 2 6 8 ]
[ 10 7 5 1 ]
[ 9 3 11 ]
/*
Node Js program
Reverse alternate levels of a binary tree
*/

//Binary Tree node
class TreeNode
{
constructor(data)
{
//set node value
this.data = data;
this.left = null;
this.right = null;
}
}
// Queue Node
class QueueNode
{
constructor(element, level)
{
this.element = element;
this.next = null;
this.level = level;
}
}
//Define custom queue class
class MyQueue
{
constructor()
{
this.front = null;
this.tail = null;
}
//Add a new node at last of queue
enqueue(element, level)
{
var new_node = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
dequeue()
{
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
is_empty()
{
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
constructor()
{
// Set initial tree root to null
this.root = null;
}
//Reverse level nodes
reverse_level(queue, level)
{
if (queue.front == null)
{
return;
}
var size = 0;
var temp = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
size++;
temp = temp.next;
}
if (size == 1)
{
//When only one element in given level
return;
}
else
{
//Useful for storing level values
var collection = Array(size).fill(0);
var location = 0;
//Start to first node
temp = queue.front;
//Get level nodes from left to right
while (temp != null && temp.level == level)
{
// Get node value
collection[location] = temp.element.data;
temp = temp.next;
// Change location
location++;
}
location = size - 1;
//Start to first node
temp = queue.front;
// Update level node with its reverse order node value
while (location >= 0 && temp != null && temp.level == level)
{
temp.element.data = collection[location];
temp = temp.next;
location--;
}
}
}
// Travers the level order nodes in binary tree and
// Display alternate reversal level nodes
reverse_alternate_level()
{
if (this.root == null)
{
process.stdout.write("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
var node = this.root;
//Create a Queue
var queue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
var temp = queue.front;
var level = 0;
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
level = 0;
//Print level nodes, and reverse alternate level elements
while (queue.is_empty() == false)
{
level = queue.front.level;
process.stdout.write(" [");
if (level % 2 == 0)
{
//This reverse level
this.reverse_level(queue, level);
}
//Print and removing queue nodes
while (queue.is_empty() == false && queue.front.level == level)
{
//When sum exist
process.stdout.write(" " + queue.front.element.data);
//remove  a queue node
queue.dequeue();
}
process.stdout.write(" ]\n");
}
}
}
}

function main()
{
//Object of Binary Tree
var tree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
7
/    \
/      \
3        4
/      /    \
2      6      8
/  \     \    /
1    5     7  10
/ \     \
9   3     11
--------------------------
*/

tree.root = new TreeNode(7);
tree.root.left = new TreeNode(3);
tree.root.right = new TreeNode(4);
tree.root.right.right = new TreeNode(8);
tree.root.right.left = new TreeNode(6);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(1);
tree.root.left.left.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(10);
tree.root.left.left.right.left = new TreeNode(9);
tree.root.left.left.right.right = new TreeNode(3);
tree.root.right.left.right.right = new TreeNode(11);
/*
Converted Binary tree
-----------------------
7
/    \
/      \
4        3   // change level
/      /    \
2      6      8
/  \     \    /
10   7     5  1   // change level
/ \     \
9   3     11
-----------------------
*/
tree.reverse_alternate_level();
}
main();

#### Output

[ 7 ]
[ 4 3 ]
[ 2 6 8 ]
[ 10 7 5 1 ]
[ 9 3 11 ]
#   Python 3 program
#   Reverse alternate levels of a binary tree

# Binary Tree node
class TreeNode :

def __init__(self, data) :
# set node value
self.data = data
self.left = None
self.right = None

#  Queue Node
class QueueNode :

def __init__(self, element, level) :
self.element = element
self.next = None
self.level = level

# Define custom queue class
class MyQueue :

def __init__(self) :
self.front = None
self.tail = None

# Add a new node at last of queue
def enqueue(self, element, level) :
new_node = QueueNode(element, level)
if (self.front == None) :
# When first node of queue
self.front = new_node
else :
# Add node at last position
self.tail.next = new_node

self.tail = new_node

# Delete first node of queue
def dequeue(self) :
if (self.front != None) :
if (self.tail == self.front) :
self.tail = None
self.front = None
else :
self.front = self.front.next

def is_empty(self) :
if (self.front == None) :
return True
else :
return False

class BinaryTree :

def __init__(self) :
#  Set initial tree root to null
self.root = None

# Reverse level nodes
def reverse_level(self, queue, level) :
if (queue.front == None) :
return

size = 0
temp = queue.front
# Count number of nodes in given level
while (temp != None and temp.level == level) :
size += 1
temp = temp.next

if (size == 1) :
# When only one element in given level
return
else :
# Useful for storing level values
collection = [0] * (size)
location = 0
# Start to first node
temp = queue.front
# Get level nodes from left to right
while (temp != None and temp.level == level) :
#  Get node value
collection[location] = temp.element.data
temp = temp.next
#  Change location
location += 1

location = size - 1
# Start to first node
temp = queue.front
#  Update level node with its reverse order node value
while (location >= 0 and temp != None and temp.level == level) :
temp.element.data = collection[location]
temp = temp.next
location -= 1

#  Travers the level order nodes in binary tree and
#  Display alternate reversal level nodes
def reverse_alternate_level(self) :
if (self.root == None) :
print("\n Empty Binary Tree \n", end = "")
else :
# Get top node in tree
node = self.root
# Create a Queue
queue = MyQueue()
# Add first node at the level of one
queue.enqueue(node, 1)
temp = queue.front
level = 0
while (temp != None) :
node = temp.element
level = temp.level
if (node.left != None) :
queue.enqueue(node.left, level + 1)

if (node.right != None) :
queue.enqueue(node.right, level + 1)

temp = temp.next

level = 0
# Print level nodes, and reverse alternate level elements
while (queue.is_empty() == False) :
level = queue.front.level
print(" [", end = "")
if (level % 2 == 0) :
# This reverse level
self.reverse_level(queue, level)

# Print and removing queue nodes
while (queue.is_empty() == False and queue.front.level == level) :
# When sum exist
print(" ", queue.front.element.data, end = "")
# remove  a queue node
queue.dequeue()

print(" ]\n", end = "")

def main() :
# Object of Binary Tree
tree = BinaryTree()
#
# 		Construct Binary Tree
# 		-----------------------
# 		            7
# 		          /    \
# 		         /      \
# 		        3        4
# 		       /      /    \
# 		      2      6      8
# 		     /  \     \    /
# 		    1    5     7  10
# 		        / \     \
# 		       9   3     11
# 		--------------------------
#

tree.root = TreeNode(7)
tree.root.left = TreeNode(3)
tree.root.right = TreeNode(4)
tree.root.right.right = TreeNode(8)
tree.root.right.left = TreeNode(6)
tree.root.left.left = TreeNode(2)
tree.root.left.left.left = TreeNode(1)
tree.root.left.left.right = TreeNode(5)
tree.root.right.left.right = TreeNode(7)
tree.root.right.right.left = TreeNode(10)
tree.root.left.left.right.left = TreeNode(9)
tree.root.left.left.right.right = TreeNode(3)
tree.root.right.left.right.right = TreeNode(11)
#
# 		Converted Binary tree
# 		-----------------------
# 		            7
# 		          /    \
# 		         /      \
# 		        4        3   // change level
# 		       /      /    \
# 		      2      6      8
# 		     /  \     \    /
# 		    10   7     5  1   // change level
# 		        / \     \
# 		       9   3     11
# 		-----------------------
#

tree.reverse_alternate_level()

if __name__ == "__main__": main()

#### Output

[  7 ]
[  4  3 ]
[  2  6  8 ]
[  10  7  5  1 ]
[  9  3  11 ]
#   Ruby program
#   Reverse alternate levels of a binary tree

# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :data, :left, :right

def initialize(data)
# set node value
self.data = data
self.left = nil
self.right = nil
end

end

#  Queue Node
class QueueNode
# Define the accessor and reader of class QueueNode
attr_accessor :element, :next, :level

def initialize(element, level)
self.element = element
self.next = nil
self.level = level
end

end

# Define custom queue class
class MyQueue
# Define the accessor and reader of class MyQueue
attr_accessor :front, :tail

def initialize()
self.front = nil
self.tail = nil
end

# Add a new node at last of queue
def enqueue(element, level)
new_node = QueueNode.new(element, level)
if (self.front == nil)
# When first node of queue
self.front = new_node
else
# Add node at last position
self.tail.next = new_node
end

self.tail = new_node
end

# Delete first node of queue
def dequeue()
if (self.front != nil)
if (self.tail == self.front)
self.tail = nil
self.front = nil
else
self.front = self.front.next
end

end

end

def is_empty()
if (self.front == nil)
return true
else
return false
end

end

end

class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_accessor :root

def initialize()
#  Set initial tree root to null
self.root = nil
end

# Reverse level nodes
def reverse_level(queue, level)
if (queue.front == nil)
return
end

size = 0
temp = queue.front
# Count number of nodes in given level
while (temp != nil && temp.level == level)
size += 1
temp = temp.next
end

if (size == 1)
# When only one element in given level
return
else
# Useful for storing level values
collection = Array.new(size) {0}
location = 0
# Start to first node
temp = queue.front
# Get level nodes from left to right
while (temp != nil && temp.level == level)
#  Get node value
collection[location] = temp.element.data
temp = temp.next
#  Change location
location += 1
end

location = size - 1
# Start to first node
temp = queue.front
#  Update level node with its reverse order node value
while (location >= 0 && temp != nil && temp.level == level)
temp.element.data = collection[location]
temp = temp.next
location -= 1
end

end

end

#  Travers the level order nodes in binary tree and
#  Display alternate reversal level nodes
def reverse_alternate_level()
if (self.root == nil)
print("\n Empty Binary Tree \n")
else
# Get top node in tree
node = self.root
# Create a Queue
queue = MyQueue.new()
# Add first node at the level of one
queue.enqueue(node, 1)
temp = queue.front
level = 0
while (temp != nil)
node = temp.element
level = temp.level
if (node.left != nil)
queue.enqueue(node.left, level + 1)
end

if (node.right != nil)
queue.enqueue(node.right, level + 1)
end

temp = temp.next
end

level = 0
# Print level nodes, and reverse alternate level elements
while (queue.is_empty() == false)
level = queue.front.level
print(" [")
if (level % 2 == 0)
# This reverse level
self.reverse_level(queue, level)
end

# Print and removing queue nodes
while (queue.is_empty() == false && queue.front.level == level)
# When sum exist
print(" ", queue.front.element.data)
# remove  a queue node
queue.dequeue()
end

print(" ]\n")
end

end

end

end

def main()
# Object of Binary Tree
tree = BinaryTree.new()
#
# 		Construct Binary Tree
# 		-----------------------
# 		            7
# 		          /    \
# 		         /      \
# 		        3        4
# 		       /      /    \
# 		      2      6      8
# 		     /  \     \    /
# 		    1    5     7  10
# 		        / \     \
# 		       9   3     11
# 		--------------------------
#

tree.root = TreeNode.new(7)
tree.root.left = TreeNode.new(3)
tree.root.right = TreeNode.new(4)
tree.root.right.right = TreeNode.new(8)
tree.root.right.left = TreeNode.new(6)
tree.root.left.left = TreeNode.new(2)
tree.root.left.left.left = TreeNode.new(1)
tree.root.left.left.right = TreeNode.new(5)
tree.root.right.left.right = TreeNode.new(7)
tree.root.right.right.left = TreeNode.new(10)
tree.root.left.left.right.left = TreeNode.new(9)
tree.root.left.left.right.right = TreeNode.new(3)
tree.root.right.left.right.right = TreeNode.new(11)
#
# 		Converted Binary tree
# 		-----------------------
# 		            7
# 		          /    \
# 		         /      \
# 		        4        3   // change level
# 		       /      /    \
# 		      2      6      8
# 		     /  \     \    /
# 		    10   7     5  1   // change level
# 		        / \     \
# 		       9   3     11
# 		-----------------------
#

tree.reverse_alternate_level()
end

main()

#### Output

[ 7 ]
[ 4 3 ]
[ 2 6 8 ]
[ 10 7 5 1 ]
[ 9 3 11 ]
/*
Scala program
Reverse alternate levels of a binary tree
*/

//Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
this(data, null, null);
}
}
// Queue Node
class QueueNode(var element: TreeNode,
var next: QueueNode,
var level: Int)
{
def this(element: TreeNode, level: Int)
{
this(element, null, level);
}
}
//Define custom queue class
class MyQueue(var front: QueueNode,
var tail: QueueNode)
{
def this()
{
this(null, null);
}
//Add a new node at last of queue
def enqueue(element: TreeNode, level: Int): Unit = {
var new_node: QueueNode = new QueueNode(element, level);
if (this.front == null)
{
//When first node of queue
this.front = new_node;
}
else
{
this.tail.next = new_node;
}
this.tail = new_node;
}
//Delete first node of queue
def dequeue(): Unit = {
if (this.front != null)
{
if (this.tail == this.front)
{
this.tail = null;
this.front = null;
}
else
{
this.front = this.front.next;
}
}
}
def is_empty(): Boolean = {
if (this.front == null)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
//Reverse level nodes
def reverse_level(queue: MyQueue, level: Int): Unit = {
if (queue.front == null)
{
return;
}
var size: Int = 0;
var temp: QueueNode = queue.front;
//Count number of nodes in given level
while (temp != null && temp.level == level)
{
size += 1;
temp = temp.next;
}
if (size == 1)
{
//When only one element in given level
return;
}
else
{
//Useful for storing level values
var collection: Array[Int] = Array.fill[Int](size)(0);
var location: Int = 0;
//Start to first node
temp = queue.front;
//Get level nodes from left to right
while (temp != null && temp.level == level)
{
// Get node value
collection(location) = temp.element.data;
temp = temp.next;
// Change location
location += 1;
}
location = size - 1;
//Start to first node
temp = queue.front;
// Update level node with its reverse order node value
while (location >= 0 && temp != null && temp.level == level)
{
temp.element.data = collection(location);
temp = temp.next;
location -= 1;
}
}
}
// Travers the level order nodes in binary tree and
// Display alternate reversal level nodes
def reverse_alternate_level(): Unit = {
if (this.root == null)
{
print("\n Empty Binary Tree \n");
}
else
{
//Get top node in tree
var node: TreeNode = this.root;
//Create a Queue
var queue: MyQueue = new MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
var temp: QueueNode = queue.front;
var level: Int = 0;
while (temp != null)
{
node = temp.element;
level = temp.level;
if (node.left != null)
{
queue.enqueue(node.left, level + 1);
}
if (node.right != null)
{
queue.enqueue(node.right, level + 1);
}
temp = temp.next;
}
level = 0;
//Print level nodes, and reverse alternate level elements
while (queue.is_empty() == false)
{
level = queue.front.level;
print(" [");
if (level % 2 == 0)
{
//This reverse level
reverse_level(queue, level);
}
//Print and removing queue nodes
while (queue.is_empty() == false && queue.front.level == level)
{
//When sum exist
print(" " + queue.front.element.data);
//remove  a queue node
queue.dequeue();
}
print(" ]\n");
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
//Object of Binary Tree
var tree: BinaryTree = new BinaryTree();
/*
Construct Binary Tree
-----------------------
7
/    \
/      \
3        4
/      /    \
2      6      8
/  \     \    /
1    5     7  10
/ \     \
9   3     11
--------------------------
*/

tree.root = new TreeNode(7);
tree.root.left = new TreeNode(3);
tree.root.right = new TreeNode(4);
tree.root.right.right = new TreeNode(8);
tree.root.right.left = new TreeNode(6);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(1);
tree.root.left.left.right = new TreeNode(5);
tree.root.right.left.right = new TreeNode(7);
tree.root.right.right.left = new TreeNode(10);
tree.root.left.left.right.left = new TreeNode(9);
tree.root.left.left.right.right = new TreeNode(3);
tree.root.right.left.right.right = new TreeNode(11);
/*
Converted Binary tree
-----------------------
7
/    \
/      \
4        3   // change level
/      /    \
2      6      8
/  \     \    /
10   7     5  1   // change level
/ \     \
9   3     11
-----------------------
*/
tree.reverse_alternate_level();
}
}

#### Output

[ 7 ]
[ 4 3 ]
[ 2 6 8 ]
[ 10 7 5 1 ]
[ 9 3 11 ]
/*
Swift 4 program
Reverse alternate levels of a binary tree
*/
//Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
//set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
// Queue Node
class QueueNode
{
var element: TreeNode? ;
var next: QueueNode? ;
var level: Int;
init(_ element: TreeNode? , _ level : Int)
{
self.element = element;
self.next = nil;
self.level = level;
}
}
//Define custom queue class
class MyQueue
{
var front: QueueNode? ;
var tail: QueueNode? ;
init()
{
self.front = nil;
self.tail = nil;
}
//Add a new node at last of queue
func enqueue(_ element: TreeNode? , _ level : Int)
{
let new_node: QueueNode? = QueueNode(element, level);
if (self.front == nil)
{
//When first node of queue
self.front = new_node;
}
else
{
self.tail!.next = new_node;
}
self.tail = new_node;
}
//Delete first node of queue
func dequeue()
{
if (self.front != nil)
{
if (self.tail === self.front)
{
self.tail = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
}
}
}
func is_empty() -> Bool
{
if (self.front == nil)
{
return true;
}
else
{
return false;
}
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
// Set initial tree root to null
self.root = nil;
}
//Reverse level nodes
func reverse_level(_ queue: MyQueue , _ level : Int)
{
if (queue.front == nil)
{
return;
}
var size: Int = 0;
var temp: QueueNode? = queue.front;
//Count number of nodes in given level
while (temp != nil && temp!.level == level)
{
size += 1;
temp = temp!.next;
}
if (size == 1)
{
//When only one element in given level
return;
}
else
{
//Useful for storing level values
var collection: [Int] = Array(repeating: 0, count: size);
var location: Int = 0;
//Start to first node
temp = queue.front;
//Get level nodes from left to right
while (temp != nil && temp!.level == level)
{
// Get node value
collection[location] = temp!.element!.data;
temp = temp!.next;
// Change location
location += 1;
}
location = size - 1;
//Start to first node
temp = queue.front;
// Update level node with its reverse order node value
while (location >= 0 && temp != nil && temp!.level == level)
{
temp!.element!.data = collection[location];
temp = temp!.next;
location -= 1;
}
}
}
// Travers the level order nodes in binary tree and
// Display alternate reversal level nodes
func reverse_alternate_level()
{
if (self.root == nil)
{
print("\n Empty Binary Tree \n", terminator: "");
}
else
{
//Get top node in tree
var node: TreeNode? = self.root;
//Create a Queue
let queue: MyQueue = MyQueue();
//Add first node at the level of one
queue.enqueue(node, 1);
var temp: QueueNode? = queue.front;
var level: Int = 0;
while (temp != nil)
{
node = temp!.element;
level = temp!.level;
if (node!.left != nil)
{
queue.enqueue(node!.left, level + 1);
}
if (node!.right != nil)
{
queue.enqueue(node!.right, level + 1);
}
temp = temp!.next;
}
level = 0;
//Print level nodes, and reverse alternate level elements
while (queue.is_empty() == false)
{
level = queue.front!.level;
print(" [", terminator: "");
if (level % 2 == 0)
{
//This reverse level
self.reverse_level(queue, level);
}
//Print and removing queue nodes
while (queue.is_empty() == false && queue.front!.level == level)
{
//When sum exist
print(" ", queue.front!.element!.data, terminator: "");
//remove  a queue node
queue.dequeue();
}
print(" ]\n", terminator: "");
}
}
}
}
func main()
{
//Object of Binary Tree
let tree: BinaryTree = BinaryTree();
/*
Construct Binary Tree
-----------------------
7
/    \
/      \
3        4
/      /    \
2      6      8
/  \     \    /
1    5     7  10
/ \     \
9   3     11
--------------------------
*/

tree.root = TreeNode(7);
tree.root!.left = TreeNode(3);
tree.root!.right = TreeNode(4);
tree.root!.right!.right = TreeNode(8);
tree.root!.right!.left = TreeNode(6);
tree.root!.left!.left = TreeNode(2);
tree.root!.left!.left!.left = TreeNode(1);
tree.root!.left!.left!.right = TreeNode(5);
tree.root!.right!.left!.right = TreeNode(7);
tree.root!.right!.right!.left = TreeNode(10);
tree.root!.left!.left!.right!.left = TreeNode(9);
tree.root!.left!.left!.right!.right = TreeNode(3);
tree.root!.right!.left!.right!.right = TreeNode(11);
/*
Converted Binary tree
-----------------------
7
/    \
/      \
4        3   // change level
/      /    \
2      6      8
/  \     \    /
10   7     5  1   // change level
/ \     \
9   3     11
-----------------------
*/
tree.reverse_alternate_level();
}
main();

#### Output

[  7 ]
[  4  3 ]
[  2  6  8 ]
[  10  7  5  1 ]
[  9  3  11 ]

## Output Explanation

The code implements the algorithm and prints the nodes of the binary tree after reversing alternate levels. It displays the nodes' values for each level in square brackets.

## Time Complexity

The time complexity of this algorithm is O(N), where N is the number of nodes in the binary tree. This is because we perform a BFS traversal through all nodes of the binary tree. The space complexity is also O(N), as we use a queue for BFS traversal.

## Comment

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.

Categories
Relative Post