Posted on by Kalkicode
Code Queue

Invert the levels of binary tree

The problem at hand involves inverting the levels of a binary tree. In other words, the nodes at each level of the tree need to be reversed in their order. This means that the leftmost node of a level should become the rightmost, and vice versa, for each level.

Problem Statement

Given a binary tree, the task is to invert the order of nodes at each level of the tree.

Example Scenario

Consider the following binary tree:

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

After inverting the levels, the tree should look like:

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

Idea to Solve the Problem

To solve this problem, we can perform a level-order traversal of the binary tree while reversing the nodes at each level. We can use a queue to traverse the tree level by level. For each level, we can reverse the order of nodes in the queue and update the tree nodes accordingly.

Pseudocode

void invert_level_nodes(struct Node *root)
{
    if (root is NULL)
    {
        return;
    }
    
    // Create a queue for level-order traversal
    // Enqueue the root node
    
    while (the queue is not empty)
    {
        // Get the number of nodes at the current level
        
        // Create an array to store node values at the current level
        
        // Dequeue nodes and store their values in the array
        
        // Update nodes' values in reverse order
        
        // Enqueue left and right children of nodes in the queue
    }
}

Algorithm Explanation

  1. Implement the invert_level_nodes function that takes the root node of the binary tree as input.
  2. Create a queue for level-order traversal using the provided enqueue function.
  3. Enqueue the root node of the tree into the queue.
  4. Start a loop that continues as long as the queue is not empty.
  5. Inside the loop, get the number of nodes at the current level and create an array to store their values.
  6. Dequeue nodes from the queue, store their values in the array, and update their values in reverse order.
  7. Enqueue the left and right children of the nodes into the queue.
  8. After the loop ends, the tree's levels will be inverted.

Code Solution

// C program
// Invert the levels of 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--;
		}
	}
}
// Traverses the level order nodes in the binary tree , // And reversing the level nodes of the tree
void invert_level_nodes(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)
			{
				//Add new left child node
				tail->next = enqueue(node->left);
				tail->next->level = level;
				tail = tail->next;
			}
			if (node->right != NULL)
			{
				//Add new right child node
				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 level elements
		while (front != NULL)
		{
			// Get node level
			level = front->level;
			reverse_level(front, level);
			printf(" [");
			//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
    
    -----------------------
    */
	
	//Add node
	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   
           /      /    \
          8      6      2
         /  \     \    /
        10   7     5  1  
            / \     \
           11   3    9
    
    -----------------------
    */
	
	invert_level_nodes(root);
	return 0;
}

Output

 [ 7 ]
 [ 4  3 ]
 [ 8  6  2 ]
 [ 10  7  5  1 ]
 [ 11  3  9 ]
/* 
  Java program 
  Invert the levels of 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
		{
			//Add node at last position
			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--;
			}
		}
	}
	// Traverses the level order nodes in the binary tree , // And reversing the level nodes of the tree
	public void invert_level_nodes()
	{
		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;
			//Add tree level
			while (temp != null)
			{
				node = temp.element;
				level = temp.level;
				if (node.left != null)
				{
					//Add left node
					queue.enqueue(node.left, level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					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(" [");
				//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
		--------------------------
		*/
		//Add node
		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   
		       /      /    \
		      2      6      8
		     /  \     \    /
		    10   7     5  1   
		        / \     \
		       9   3     11
		-----------------------
		*/
		tree.invert_level_nodes();
	}
}

Output

 [ 7 ]
 [ 4 3 ]
 [ 8 6 2 ]
 [ 10 7 5 1 ]
 [ 11 3 9 ]
//Include header file
#include <iostream>
using namespace std;

/*
  C++ program 
  Invert the levels of 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
		{
			//Add node at last position
			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--;
			}
		}
	}
	// Traverses the level order nodes in the binary tree , // And reversing the level nodes of the tree
	void invert_level_nodes()
	{
		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;
			//Add tree level
			while (temp != NULL)
			{
				node = temp->element;
				level = temp->level;
				if (node->left != NULL)
				{
					//Add left node
					queue.enqueue(node->left, level + 1);
				}
				if (node->right != NULL)
				{
					//Add right node
					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 << " [";
				//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   
			       /      /    \
			      2      6      8
			     /  \     \    /
			    10   7     5  1   
			        / \     \
			       9   3     11
			-----------------------
			*/
	tree.invert_level_nodes();
	return 0;
}

Output

 [ 7 ]
 [ 4 3 ]
 [ 8 6 2 ]
 [ 10 7 5 1 ]
 [ 11 3 9 ]
//Include namespace system
using System;
/* 
  C# program 
  Invert the levels of 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
		{
			//Add node at last position
			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--;
			}
		}
	}
	// Traverses the level order nodes in the binary tree , // And reversing the level nodes of the tree
	public void invert_level_nodes()
	{
		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;
			//Add tree level
			while (temp != null)
			{
				node = temp.element;
				level = temp.level;
				if (node.left != null)
				{
					//Add left node
					queue.enqueue(node.left, level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					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(" [");
				//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   
				       /      /    \
				      2      6      8
				     /  \     \    /
				    10   7     5  1   
				        / \     \
				       9   3     11
				-----------------------
		*/
		tree.invert_level_nodes();
	}
}

Output

 [ 7 ]
 [ 4 3 ]
 [ 8 6 2 ]
 [ 10 7 5 1 ]
 [ 11 3 9 ]
<?php
/* 
  Php program 
  Invert the levels of 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
		{
			//Add node at last position
			$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--;
			}
		}
	}
	// Traverses the level order nodes in the binary tree , // And reversing the level nodes of the tree
	public	function invert_level_nodes()
	{
		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;
			//Add tree level
			while ($temp != null)
			{
				$node = $temp->element;
				$level = $temp->level;
				if ($node->left != null)
				{
					//Add left node
					$queue->enqueue($node->left, $level + 1);
				}
				if ($node->right != null)
				{
					//Add right node
					$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 " [";
				//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
	--------------------------
	*/

	//Add node
	$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   
			       /      /    \
			      2      6      8
			     /  \     \    /
			    10   7     5  1   
			        / \     \
			       9   3     11
	-----------------------
	*/
	$tree->invert_level_nodes();
}
main();

Output

 [ 7 ]
 [ 4 3 ]
 [ 8 6 2 ]
 [ 10 7 5 1 ]
 [ 11 3 9 ]
/* 
  Node Js program 
  Invert the levels of 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
		{
			//Add node at last position
			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--;
			}
		}
	}
	// Traverses the level order nodes in the binary tree , // And reversing the level nodes of the tree
	invert_level_nodes()
	{
		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;
			//Add tree level
			while (temp != null)
			{
				node = temp.element;
				level = temp.level;
				if (node.left != null)
				{
					//Add left node
					queue.enqueue(node.left, level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					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(" [");
				//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
	--------------------------
	*/
	//Add node
	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   
			       /      /    \
			      2      6      8
			     /  \     \    /
			    10   7     5  1   
			        / \     \
			       9   3     11
	-----------------------
	*/
	tree.invert_level_nodes();
}
main();

Output

 [ 7 ]
 [ 4 3 ]
 [ 8 6 2 ]
 [ 10 7 5 1 ]
 [ 11 3 9 ]
#   Python 3 program 
#   Invert the levels of 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
			
		
	
	#  Traverses the level order nodes in the binary tree , // And reversing the level nodes of the tree
	def invert_level_nodes(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
			# Add tree level
			while (temp != None) :
				node = temp.element
				level = temp.level
				if (node.left != None) :
					# Add left node
					queue.enqueue(node.left, level + 1)
				
				if (node.right != None) :
					# Add right node
					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 = "")
				# 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
	# 		--------------------------
	# 		
	

	# Add node
	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   
	# 		       /      /    \
	# 		      2      6      8
	# 		     /  \     \    /
	# 		    10   7     5  1   
	# 		        / \     \
	# 		       9   3     11
	# 		-----------------------
	# 		
	
	tree.invert_level_nodes()

if __name__ == "__main__": main()

Output

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

# Binary Tree node
class TreeNode  
	# Define the accessor and reader of class TreeNode  
	attr_reader :data, :left, :right
	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_reader :element, :next, :level
	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_reader :front, :tail
	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_reader :root
	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

	#  Traverses the level order nodes in the binary tree , // And reversing the level nodes of the tree
	def invert_level_nodes() 
		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
			# Add tree level
			while (temp != nil) 
				node = temp.element
				level = temp.level
				if (node.left != nil) 
					# Add left node
					queue.enqueue(node.left, level + 1)
				end

				if (node.right != nil) 
					# Add right node
					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(" [")
				# 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)
					# 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
	# 		--------------------------
	# 		
	
	# Add node
	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   
	# 		       /      /    \
	# 		      2      6      8
	# 		     /  \     \    /
	# 		    10   7     5  1   
	# 		        / \     \
	# 		       9   3     11
	# 		-----------------------
	# 		
	
	tree.invert_level_nodes()
end

main()

Output

 [ 7 ]
 [ 4 3 ]
 [ 8 6 2 ]
 [ 10 7 5 1 ]
 [ 11 3 9 ]
/* 
  Scala program 
  Invert the levels of 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
		{
			//Add node at last position
			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;
			}
		}
	}
	// Traverses the level order nodes in the binary tree , // And reversing the level nodes of the tree
	def invert_level_nodes(): 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;
			//Add tree level
			while (temp != null)
			{
				node = temp.element;
				level = temp.level;
				if (node.left != null)
				{
					//Add left node
					queue.enqueue(node.left, level + 1);
				}
				if (node.right != null)
				{
					//Add right node
					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(" [");
				//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
		--------------------------
		*/
		
		//Add node
		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  
				       /      /    \
				      2      6      8
				     /  \     \    /
				    10   7     5  1   
				        / \     \
				       9   3     11
		-----------------------
		*/
		tree.invert_level_nodes();
	}
}

Output

 [ 7 ]
 [ 4 3 ]
 [ 8 6 2 ]
 [ 10 7 5 1 ]
 [ 11 3 9 ]
/* 
  Swift 4 program 
  Invert the levels of 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
		{
			//Add node at last position
			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;
			}
		}
	}
	// Traverses the level order nodes in the binary tree , // And reversing the level nodes of the tree
	func invert_level_nodes()
	{
		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;
			//Add tree level
			while (temp != nil)
			{
				node = temp!.element;
				level = temp!.level;
				if (node!.left != nil)
				{
					//Add left node
					queue.enqueue(node!.left, level + 1);
				}
				if (node!.right != nil)
				{
					//Add right node
					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: "");
				//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   
			       /      /    \
			      2      6      8
			     /  \     \    /
			    10   7     5  1  
			        / \     \
			       9   3     11
	-----------------------
	*/
	tree.invert_level_nodes();
}
main();

Output

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

Output Explanation

The code implements the algorithm and inverts the levels of the given binary tree. It constructs the binary tree, performs the level-order traversal while reversing the nodes' values at each level, and then prints the resulting inverted levels.

Time Complexity

The time complexity of this algorithm depends on the level-order traversal of the tree. If there are N nodes in the tree, the time complexity is O(N) as each node is processed once. The space complexity is also O(N) due to the queue used for 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.

New Comment