Given a binary tree and an integer K, the task is to print the level order traversal in such a way that first K levels are printed from left to right, next K levels are printed from right to left, then next K levels are from left to right and so on.
Examples:
Input: K = 1
1
/ \
2 3
/ \ /
4 9 8
Output:
1
3 2
4 9 8
Explanation: In the above example, first level is printed from left to right
and the second level is printed from right to left, and then last level is
printed from left to right.Input: K = 3
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ /
8 9 10 11 12
/ \ /
13 14 15Output:
1
2 3
4 5 6 7
12 11 10 9 8
15 14 13
Explanation: In the above example, first 3 levels are printed from left to right
and the last 2 levels are printed from right to left.
Approach: The solution to the problem is based on the following idea:
Start performing level order traversal on the tree from the left most end. After every K level, change the direction of printing the elements.
For this use stack. When the levels are to be printed from the right keep those values in stack and print the stack elements one by one from top. Because of the last in first out property of stack the elements would printed in reverse order.
Follow the steps mentioned below to implement the above idea:
- Use queue to perform level order traversal.
- In each level:
- If it is to be printed from the left, print them and push their child nodes in the queue.
- If this level is to be printed from the right side push the elements in a stack and print them after the whole level is traversed.
- If K levels are covered change the direction of printing from the next one.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Binary Tree nodestruct Node { int data; Node *left, *right;};// Function that returns a new nodeNode* newNode(int data){ Node* temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp;}// Function to print the level order of tree// by reversing the direction of traversal// after every n levelsvoid traverse(Node* root, int n){ // NULL check if (!root) return; // Queue for level order traversal queue<Node*> q; // Stack for // reverse level order traversal stack<Node*> s; // For changing the direction // of traversal bool right2left = false; // To count number of levels int count = 0; q.push(root); while (!q.empty()) { int size = q.size(); count++; while (size--) { root = q.front(); q.pop(); // Prints the nodes from // left to right if (right2left == false) cout << root->data << " "; // Push the nodes into stack // for printing from right to left else s.push(root); if (root->left) q.push(root->left); if (root->right) q.push(root->right); } // If the condition satisfies // prints the nodes from right to left. if (right2left == true) { while (!s.empty()) { cout << s.top()->data << " "; s.pop(); } } // If the count becomes n // then reverse the direction if (count == n) { right2left = !right2left; // Update the count to 0 count = 0; } cout << endl; }}int main(){ // Create a Binary Tree 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->right->left->right = newNode(11); root->right->right->left = newNode(12); root->left->left->right->left = newNode(13); root->left->left->right->right = newNode(14); root->right->left->right->left = newNode(15); // Specify K to change the direction // after every K levels. int K = 3; traverse(root, K); return 0;} |
Java
import java.util.*;import java.io.*;// Java program for the above approachclass GFG{ // Binary Tree node static class Node{ int data; Node left, right; Node(int data){ this.data = data; left = null; right = null; } } // Function to print the level order of tree // by reversing the direction of traversal // after every n levels. public static void traverse(Node root, int n){ // Null check if(root == null){ return; } // Queue for level order traversal Queue<Node> q = new ArrayDeque<Node>(); // Stack for // reverse level order traversal Stack<Node> s = new Stack<Node>(); // For changing the direction of traversal Boolean right2left = false; // To count number of levels int count = 0; q.add(root); while(!q.isEmpty()){ int size = q.size(); count++; while(size > 0){ size--; root = q.peek(); q.remove(); // Prints the nodes from left to right if(right2left == false){ System.out.print(root.data + " "); } // Push the nodes into stack // for printing from right to left else{ s.push(root); } if(root.left != null){ q.add(root.left); } if(root.right != null){ q.add(root.right); } } // If the condition satisfies // prints the nodes from right to left. if(right2left == true){ while(!s.isEmpty()){ Node topElement = s.pop(); System.out.print(topElement.data + " "); } } // If the count becomes n // then reverse the direction if(count == n){ right2left = !right2left; // Update the count to 0 count = 0; } System.out.println(""); } } // Driver code public static void main(String args[]) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.right.left.right = new Node(11); root.right.right.left = new Node(12); root.left.left.right.left = new Node(13); root.left.left.right.right = new Node(14); root.right.left.right.left = new Node(15); // Specify K to change the direction // after every K levels. int K = 3; traverse(root, K); }}// This code is contributed by subhamgoyal2014. |
Python3
# Python code for the above approach# Binary Tree nodeclass Node: def __init__(self, d): self.data = d self.left = None self.right = None# Function to print the level order of tree# by reversing the direction of traversal# after every n levelsdef traverse(root, n): # NULL check if (root == None): return # Queue for level order traversal q = [] # Stack for # reverse level order traversal s =[] # For changing the direction # of traversal right2left = False # To count number of levels count = 0 q.append(root) while(len(q) != 0): size = len(q) count += 1 while (size > 0): root = q[0] q = q[1:] # Prints the nodes from # left to right if (right2left == False): print(root.data, end = " ") # Push the nodes into stack # for printing from right to left else: s.append(root) if (root.left): q.append(root.left) if (root.right): q.append(root.right) size -= 1 # If the condition satisfies # prints the nodes from right to left. if (right2left == True): while (len(s) > 0): print(s[-1].data,end = " ") s.pop() # If the count becomes n # then reverse the direction if (count == n): right2left = not right2left # Update the count to 0 count = 0 print("")# Create a Binary Treeroot = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)root.right.left = Node(6)root.right.right = Node(7)root.left.left.left = Node(8)root.left.left.right = Node(9)root.left.right.left = Node(10)root.right.left.right = Node(11)root.right.right.left = Node(12)root.left.left.right.left = Node(13)root.left.left.right.right = Node(14)root.right.left.right.left = Node(15)# Specify K to change the direction# after every K levels.K = 3traverse(root, K)# This code is contributed by shinjanpatra |
C#
// C# code to implement the above approachusing System;using System.Collections.Generic;public class Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }}public class BinaryTree { Node root; public BinaryTree() { root = null; } public void Traverse(Node root, int n) { if (root == null) return; Queue<Node> q = new Queue<Node>(); Stack<Node> s = new Stack<Node>(); bool right2left = false; int count = 0; q.Enqueue(root); while (q.Count != 0) { int size = q.Count; count++; while (size-- > 0) { root = q.Dequeue(); if (right2left == false) Console.Write(root.data + " "); else s.Push(root); if (root.left != null) q.Enqueue(root.left); if (root.right != null) q.Enqueue(root.right); } if (right2left == true) { while (s.Count != 0) { Console.Write(s.Pop().data + " "); } } if (count == n) { right2left = !right2left; count = 0; } Console.WriteLine(); } } public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); // Create a Binary Tree tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.left.left.left = new Node(8); tree.root.left.left.right = new Node(9); tree.root.left.right.left = new Node(10); tree.root.right.left.right = new Node(11); tree.root.right.right.left = new Node(12); tree.root.left.left.right.left = new Node(13); tree.root.left.left.right.right = new Node(14); tree.root.right.left.right.left = new Node(15); // Specify K to change the direction // after every K levels. int K = 3; tree.Traverse(tree.root, K); }}// This code is contributed by adityamaharshi21 |
Javascript
<script> // JavaScript code for the above approach// Binary Tree nodeclass Node { constructor(d) { this.data = d; this.left = null; this.right = null; }};// Function to print the level order of tree// by reversing the direction of traversal// after every n levelsfunction traverse(root, n){ // NULL check if (root==null) return; // Queue for level order traversal let q = []; // Stack for // reverse level order traversal let s =[]; // For changing the direction // of traversal let right2left = false; // To count number of levels let count = 0; q.push(root); while (q.length!=0) { let size = q.length; count++; while (size--) { root = q[0]; q.shift(root); // Prints the nodes from // left to right if (right2left == false) document.write(root.data + " ") // Push the nodes into stack // for printing from right to left else s.push(root); if (root.left) q.push(root.left); if (root.right) q.push(root.right); } // If the condition satisfies // prints the nodes from right to left. if (right2left == true) { while (s.length!=0) { document.write(s[s.length-1].data + " ") s.pop(); } } // If the count becomes n // then reverse the direction if (count == n) { right2left = !right2left; // Update the count to 0 count = 0; } document.write('<br>') }} // Create a Binary Tree let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(10); root.right.left.right = new Node(11); root.right.right.left = new Node(12); root.left.left.right.left = new Node(13); root.left.left.right.right = new Node(14); root.right.left.right.left = new Node(15); // Specify K to change the direction // after every K levels. let K = 3; traverse(root, K); // This code is contributed by Potta Lokesh </script> |
Output
1 2 3 4 5 6 7 12 11 10 9 8 15 14 13
Time Complexity: O(N) where N is number of nodes
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
