Level order traversal with direction change after every two levels

Algorithm

• Here, we'll use queue and stack. The queue is used to traverse levels in the normal sequence. After every two levels, the stack is utilized to reverse the direction of traversal.
• The first two levels of nodes are printed when they are popped out of the queue during normal level order traversal.
• We pushed the nodes into the stack instead of printing them on the following two levels. We print the nodes in the stack once the current level's nodes have been pushed out.
• We can print the nodes in a right-to-left order by utilizing the stack.
• For the next two levels, we'll output nodes from left to the right using the standard level order traversal method. The stack is then used to achieve right-to-left order on the next two nodes.
• By combining queue and stack, we'll be able to achieve the necessarily modified level order traversal.

C++ Code

/* C++ program to print level order traversal with direction change after every two levels */
#include <iostream>
#include <queue>
#include <stack>

using namespace std;

/* Binary Tree Node initialization */
struct Node
{
	struct Node* left;
	int data;
	struct Node* right;
};

/* function to print the level order of given binary tree */
void printRequiredLevelOrder(struct Node* node)
{
	/* checking for null condition */
	if (node == NULL)
		return;

	if (node->left == NULL && node->right == NULL)
	{
		cout << node->data;
		return;
	}

	/* Maintain a queue for traversing the levels in the typical sequence. */
	queue<Node*> myQueue;

	/* Keep a stack for printing nodes in reverse order once they've been popped out of the queue.*/
	stack<Node*> myStack;

	struct Node* temp = NULL;

	int sz;
	int ct = 0;
	bool rightToLeft = false;

	/* Push root node to the queue */
	myQueue.push(node);

	/* Repeat this while loop until the queue is empty. */
	while (!myQueue.empty())
	{
		ct++;
		sz = myQueue.size();

		for (int i = 0; i < sz; i++) {
    		
			temp = myQueue.front();
			myQueue.pop();

			/*Simply print the nodes in the order that they are being popped out of the queue to print them from left to right.*/
			if (rightToLeft == false) {
    			cout << temp->data << " "; 
			}

			/* Push the nodes to stack instead of printing them if you want to print them from right to left.*/
			else {
    			myStack.push(temp);
			}

			if (temp->left)
				myQueue.push(temp->left);

			if (temp->right)
				myQueue.push(temp->right);
		}

		if (rightToLeft == true)
		{
			while (!myStack.empty())
			{
				temp = myStack.top();
				myStack.pop();

				cout << temp->data << " ";
			}
		}

		/*Change the direction of printing nodes after every two levels.*/
		if (ct == 2)
		{
			rightToLeft = !rightToLeft;
			ct = 0;
		}

		cout << "\n";
	}
}

/* function to create a new node */
Node* newNode(int data)
{
	Node* temp = new Node;
	temp->data = data;
	temp->left = temp->right = NULL;
	return temp;
}

/* Main Program */
int main()
{
	/* Binary tree creation */
	Node* root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);
	root->right->left = newNode(6);
	root->right->right = newNode(7);
	root->left->left->left = newNode(8);
	root->left->left->right = newNode(9);
	root->left->right->left = newNode(10);
	root->left->right->right = newNode(11);
	root->right->left->left = newNode(12);
	root->right->left->right = newNode(13);
	root->right->right->left = newNode(14);
	root->right->right->right = newNode(15);

	printRequiredLevelOrder(root);

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java Code

/* Java program to print level order traversal with direction change after every two levels */
import java.util.*;

class Main
{

    /* Binary Tree Node initialization */
    static class Node
    {
     	Node left;
     	int data;
     	Node right;
    };
    
    /* function to print the level order of given binary tree */
    static void printRequiredLevelOrder(Node node)
    {
     	/* checking for null condition */
     	if (node == null)
     		return;
    	
     	if (node.left == null && node.right == null)
     	{
     		System.out.print(node.data);
     		return;
     	}
    	
     	/* Maintain a queue for traversing the levels in the typical sequence. */
     	Queue<Node> myQueue = new LinkedList<>();
    	
     	/* Keep a stack for printing nodes in reverse order once they've been popped out of the queue.*/
     	Stack<Node> myStack = new Stack<>();
    	
     	Node temp = null;
    	
     	int sz;
     	int ct = 0;
     	boolean rightToLeft = false;
    	
     	/* Push root node to the queue */
     	myQueue.add(node);
    	
     	/* Repeat this while loop until the queue is empty. */
     	while (!myQueue.isEmpty())
     	{
     		ct++;
     		sz = myQueue.size();
     		
     		for (int i = 0; i < sz; i++) {
         		
     			temp = myQueue.peek();
     			myQueue.remove();
    			
     			/*Simply print the nodes in the order that they are being popped out of the queue to print them from left to right.*/
     			if (rightToLeft == false)
     				System.out.print(temp.data + " "); 
    			
     			/* Push the nodes to stack instead of printing them if you want to print them from right to left.*/
     			else
     				myStack.push(temp); 
    			
     			if (temp.left != null)
     				myQueue.add(temp.left);
    			
     			if (temp.right != null)
     				myQueue.add(temp.right);
     		}
    		
     		if (rightToLeft == true)
     		{
     			while (!myStack.isEmpty())
     			{
     				temp = myStack.peek();
     				myStack.pop();
    		
     				System.out.print(temp.data + " ");
     			}
     		}
    		
     		/*Change the direction of printing nodes after every two levels.*/
     		if (ct == 2)
     		{
     			rightToLeft = !rightToLeft;
     			ct = 0;
     		}
    		
     			System.out.print("\n");
     	}
    }
    
    /* function to create a new node */
    static Node newNode(int data)
    {
     	Node temp = new Node();
     	temp.data = data;
     	temp.left = temp.right = null;
     	return temp;
    }
    
    /* Main Program */
    public static void main(String[] args)
    {
     	/* Binary tree creation */
     	Node root = newNode(1);
     	root.left = newNode(2);
     	root.right = newNode(3);
     	root.left.left = newNode(4);
     	root.left.right = newNode(5);
     	root.right.left = newNode(6);
     	root.right.right = newNode(7);
     	root.left.left.left = newNode(8);
     	root.left.left.right = newNode(9);
     	root.left.right.left = newNode(10);
     	root.left.right.right = newNode(11);
     	root.right.left.left = newNode(12);
     	root.right.left.right = newNode(13);
     	root.right.right.left = newNode(14);
     	root.right.right.right = newNode(15);
     	
     	printRequiredLevelOrder(root);
    }
}

You can also try this code with Online Java Compiler

Run Code

Input

Output

1 
2 3 
7 6 5 4 
15 14 13 12 11 10 9 8

Complexities

Time complexity 

O(n),
Reason: When executing level order traversal, each node is explored at most twice so that the time complexity will be O(n).

Space complexity

O(1),
Reason: No extra space required.

Frequently Asked Questions

What are binary trees, and how do they work?

It is a non-linear data structure of the tree type with a maximum of two offspring per parent. The root node is the node at the very top of a tree's hierarchy. The parent nodes are the nodes that include additional sub-nodes.

What is the purpose of binary trees?

Binary trees are mostly used in computing for searching and sorting since they allow data to be stored hierarchically. Insertion, deletion, and traversal are some of the most frequent operations performed on binary trees.

What are the different types of Binary Trees?

Following are the different types of binary trees: full binary tree, perfect binary tree, skewed binary tree, complete binary tree, and degenerate binary tree.

Is it possible for a binary search tree to have duplicates?

No, because a search tree has no advantage in allowing duplicates because searching for one value in a binary search tree can only provide one value, not two or more.

What is the best way to find the preOrder traversal?

We can use the preOrder traversal's recursive definition to visit the root, recursively travel to the left subtree, and then proceed to the right subtree.

Conclusion

In this article, we have tried to print the level order traversal with direction change after every two levels. We hope that this blog will help you understand the concept of a binary tree, and if you want to learn more about the binary tree, check out our other blogs on the binary tree, an introduction to binary tree, binary search tree, and Binary Tree Postorder Traversal.

Recommended problems -

• Preorder Traversal
• Zig Zag Tree Traversal 
• Reverse a Stack using Recursion
   

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!