Given a Binary Search Tree, the task is to print the nodes of the BST in the following order:
- If the BST contains levels numbered from 1 to N then, the printing order is level 1, level N, level 2, level N – 1, and so on.
- The top-level order (1, 2, …) nodes are printed from left to right, while the bottom level order (N, N-1, …) nodes are printed from right to left.
Examples:
Input:
Output: 27 42 31 19 10 14 35
Explanation:
Level 1 from left to right: 27
Level 3 from right to left: 42 31 19 10
Level 2 from left to right: 14 35Input:
Output: 25 48 38 28 12 5 20 36 40 30 22 10
Approach: To solve the problem, the idea is to store the nodes of BST in ascending and descending order of levels and node values and print all the nodes of the same level alternatively between ascending and descending order. Follow the steps below to solve the problem:
- Initialize a Min Heap and a Max Heap to store the nodes in ascending and descending order of level and node values respectively.
- Perform a level order traversal on the given BST to store the nodes in the respective priority queues.
- Print all the nodes of each level one by one from the Min Heap followed by the Max Heap alternately.
- If any level in the Min Heap or Max Heap is found to be already printed, skip to the next level.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure of a BST nodestruct node { int data; struct node* left; struct node* right;};// Utility function to create a new BST nodestruct node* newnode(int d){ struct node* temp = (struct node*)malloc(sizeof(struct node)); temp->left = NULL; temp->right = NULL; temp->data = d; return temp;}// Function to print the nodes of a// BST in Top Level Order and Reversed// Bottom Level Order alternativelyvoid printBST(node* root){ // Stores the nodes in descending order // of the level and node values priority_queue<pair<int, int> > great; // Stores the nodes in ascending order // of the level and node values priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > small; // Initialize a stack for // level order traversal stack<pair<node*, int> > st; // Push the root of BST // into the stack st.push({ root, 1 }); // Perform Level Order Traversal while (!st.empty()) { // Extract and pop the node // from the current level node* curr = st.top().first; // Stores level of current node int level = st.top().second; st.pop(); // Store in the priority queues great.push({ level, curr->data }); small.push({ level, curr->data }); // Traverse left subtree if (curr->left) st.push({ curr->left, level + 1 }); // Traverse right subtree if (curr->right) st.push({ curr->right, level + 1 }); } // Stores the levels that are printed unordered_set<int> levelsprinted; // Print the nodes in the required manner while (!small.empty() && !great.empty()) { // Store the top level of traversal int toplevel = small.top().first; // If the level is already printed if (levelsprinted.find(toplevel) != levelsprinted.end()) break; // Otherwise else levelsprinted.insert(toplevel); // Print nodes of same level while (!small.empty() && small.top().first == toplevel) { cout << small.top().second << " "; small.pop(); } // Store the bottom level of traversal int bottomlevel = great.top().first; // If the level is already printed if (levelsprinted.find(bottomlevel) != levelsprinted.end()) { break; } else { levelsprinted.insert(bottomlevel); } // Print the nodes of same level while (!great.empty() && great.top().first == bottomlevel) { cout << great.top().second << " "; great.pop(); } }}// Driver Codeint main(){ /* Given BST 25 / \ 20 36 / \ / \ 10 22 30 40 / \ / / \ 5 12 28 38 48 */ // Creating the BST node* root = newnode(25); root->left = newnode(20); root->right = newnode(36); root->left->left = newnode(10); root->left->right = newnode(22); root->left->left->left = newnode(5); root->left->left->right = newnode(12); root->right->left = newnode(30); root->right->right = newnode(40); root->right->left->left = newnode(28); root->right->right->left = newnode(38); root->right->right->right = newnode(48); // Function Call printBST(root); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;public class GFG { // Structure of a BST node static class node { int data; node left; node right; } //Structure of pair (used in PriorityQueue) static class pair{ int x,y; pair(int xx, int yy){ this.x=xx; this.y=yy; } } //Structure of pair (used in Stack) static class StackPair{ node n; int x; StackPair(node nn, int xx){ this.n=nn; this.x=xx; } } // Utility function to create a new BST node static node newnode(int d) { node temp = new node(); temp.left = null; temp.right = null; temp.data = d; return temp; } //Custom Comparator for pair class to sort //elements in increasing order static class IncreasingOrder implements Comparator<pair>{ public int compare(pair p1, pair p2){ if(p1.x>p2.x){ return 1; }else{ if(p1.x<p2.x){ return -1; }else{ if(p1.y>p2.y){ return 1; }else{ if(p1.y<p2.y){ return -1; }else{ return 0; } } } } } } // Custom Comparator for pair class to sort // elements in decreasing order static class DecreasingOrder implements Comparator<pair>{ public int compare(pair p1, pair p2){ if(p1.x>p2.x){ return -1; }else{ if(p1.x<p2.x){ return 1; }else{ if(p1.y>p2.y){ return -1; }else{ if(p1.y<p2.y){ return 1; }else{ return 0; } } } } } } // Function to print the nodes of a // BST in Top Level Order and Reversed // Bottom Level Order alternatively static void printBST(node root) { // Stores the nodes in descending order // of the level and node values PriorityQueue<pair> great = new PriorityQueue<>(new DecreasingOrder()); // Stores the nodes in ascending order // of the level and node values PriorityQueue<pair> small = new PriorityQueue<>(new IncreasingOrder()); // Initialize a stack for // level order traversal Stack<StackPair> st = new Stack<>(); // Push the root of BST // into the stack st.push(new StackPair(root,1)); // Perform Level Order Traversal while (!st.isEmpty()) { // Extract and pop the node // from the current level StackPair sp = st.pop(); node curr = sp.n; // Stores level of current node int level = sp.x; // Store in the priority queues great.add(new pair(level,curr.data)); small.add(new pair(level,curr.data)); // Traverse left subtree if (curr.left!=null) st.push(new StackPair(curr.left,level+1)); // Traverse right subtree if (curr.right!=null) st.push(new StackPair(curr.right,level+1)); } // Stores the levels that are printed HashSet<Integer> levelsprinted = new HashSet<>(); // Print the nodes in the required manner while (!small.isEmpty() && !great.isEmpty()) { // Store the top level of traversal int toplevel = small.peek().x; // If the level is already printed if (levelsprinted.contains(toplevel)) break; // Otherwise else levelsprinted.add(toplevel); // Print nodes of same level while (!small.isEmpty() && small.peek().x == toplevel) { System.out.print(small.poll().y + " "); } // Store the bottom level of traversal int bottomlevel = great.peek().x; // If the level is already printed if (levelsprinted.contains(bottomlevel)) { break; } else { levelsprinted.add(bottomlevel); } // Print the nodes of same level while (!great.isEmpty() && great.peek().x == bottomlevel) { System.out.print(great.poll().y + " "); } } } public static void main (String[] args) { /* Given BST 25 / \ 20 36 / \ / \ 10 22 30 40 / \ / / \ 5 12 28 38 48 */ // Creating the BST node root = newnode(25); root.left = newnode(20); root.right = newnode(36); root.left.left = newnode(10); root.left.right = newnode(22); root.left.left.left = newnode(5); root.left.left.right = newnode(12); root.right.left = newnode(30); root.right.right = newnode(40); root.right.left.left = newnode(28); root.right.right.left = newnode(38); root.right.right.right = newnode(48); // Function Call printBST(root); }}// This code is contributed by shruti456rawal |
Python3
import queue# Structure of a BST nodeclass Node: def __init__(self, d): self.data = d self.left = None self.right = None# Function to print the nodes of a# BST in Top Level Order and Reversed# Bottom Level Order alternativelydef printBST(root): # Stores the nodes in descending order # of the level and node values great = queue.PriorityQueue() # Stores the nodes in ascending order # of the level and node values small = queue.PriorityQueue() # Initialize a queue for # level order traversal q = queue.Queue() # Push the root of BST # into the queue q.put((root, 1)) # Perform Level Order Traversal while not q.empty(): # Extract and pop the node # from the current level curr, level = q.get() # Store in the priority queues great.put((-level, curr.data)) small.put((level, curr.data)) # Traverse left subtree if curr.left: q.put((curr.left, level + 1)) # Traverse right subtree if curr.right: q.put((curr.right, level + 1)) # Stores the levels that are printed levelsprinted = set() # Print the nodes in the required manner while not small.empty() and not great.empty(): # Store the top level of traversal toplevel = small.queue[0][0] # If the level is already printed if toplevel in levelsprinted: break # Otherwise else: levelsprinted.add(toplevel) # Print nodes of same level while not small.empty() and small.queue[0][0] == toplevel: print(small.get()[1], end=' ') # Store the bottom level of traversal bottomlevel = -great.queue[0][0] # If the level is already printed if bottomlevel in levelsprinted: break else: levelsprinted.add(bottomlevel) # Print the nodes of same level while not great.empty() and -great.queue[0][0] == bottomlevel: print(great.get()[1], end=' ')# Driver Codeif __name__ == '__main__': """ Given BST 25 / \ 20 36 / \ / \ 10 22 30 40 / \ / / \ 5 12 28 38 48 """ # Creating the BST root = Node(25) root.left = Node(20) root.right = Node(36) root.left.left = Node(10) root.left.right = Node(22) root.left.left.left = Node(5) root.left.left.right = Node(12) root.right.left = Node(30) root.right.right = Node(40) root.right.left.left = Node(28) root.right.right.left = Node(38) root.right.right.right = Node(48) # Function Call printBST(root) |
C#
using System;using System.Collections.Generic;class TreeNode { public int value; public TreeNode left, right; public TreeNode(int value) { this.value = value; left = null; right = null; }}class Program { static List<List<int> > GetLevelOrderTraversal(TreeNode root) { List<List<int> > ans = new List<List<int> >(); // This will store values of nodes for the level // which we are currently traversing List<int> currentLevel = new List<int>(); // We will be pushing null at the end of each level, // So whenever we encounter a null, it means we have // traversed all the nodes of the previous level Queue<TreeNode> q = new Queue<TreeNode>(); q.Enqueue(root); q.Enqueue(null); while (q.Count > 1) { TreeNode currentNode = q.Dequeue(); if (currentNode == null) { ans.Add(currentLevel); currentLevel = new List<int>(); if (q.Count == 0) { // It means no more level to be // traversed return ans; } else { q.Enqueue(null); } } else { currentLevel.Add(currentNode.value); if (currentNode.left != null) { q.Enqueue(currentNode.left); } if (currentNode.right != null) { q.Enqueue(currentNode.right); } } } ans.Add(currentLevel); return ans; } static void Main(string[] args) { /* Given BST 25 / \ 20 36 / \ / \ 10 22 30 40 / \ / / \ 5 12 28 38 48 */ // Creating the BST TreeNode root = new TreeNode(25); root.left = new TreeNode(20); root.right = new TreeNode(36); root.left.left = new TreeNode(10); root.left.right = new TreeNode(22); root.left.left.left = new TreeNode(5); root.left.left.right = new TreeNode(12); root.right.left = new TreeNode(30); root.right.right = new TreeNode(40); root.right.left.left = new TreeNode(28); root.right.right.left = new TreeNode(38); root.right.right.right = new TreeNode(48); // Getting the value of nodes level wise List<List<int> > levelOrderTraversal = GetLevelOrderTraversal(root); // Now traversing the tree alternatively from top // and bottom using 2 pointers int i = 0; int j = levelOrderTraversal.Count - 1; while (i <= j) { if (i != j) { for (int k = 0; k < levelOrderTraversal[i].Count; k++) { Console.Write(levelOrderTraversal[i][k] + " "); } for (int k = levelOrderTraversal[j].Count - 1; k >= 0; k--) { Console.Write(levelOrderTraversal[j][k] + " "); } } else { // This will take care of the case when we // have odd number of levels in a BST for (int k = 0; k < levelOrderTraversal[i].Count; k++) { Console.Write(levelOrderTraversal[i][k] + " "); } } i++; j--; } }}// This Code is contributed by Gaurav_Arora |
Output:
25 48 38 28 12 5 20 36 40 30 22 10
Time Complexity: O(V log(V)), where V denotes the number of vertices in the given Binary Tree
Auxiliary Space: O(V)
Iterative Method(using queue):
Follow the steps to solve the given problem:
1). Perform level order traversal and keep track to level at each vertex of given tree.
2). Declare a queue to perform level order traversal and a vector of vector to store the level order traversal respectively to levels of given binary tree.
3). After storing all the vertex level wise we will initialize two iterator first will print data in level order and second will print the reverse level order and after printing the we will first first iterator and decrease the second iterator.
Below is the implementation of above approach:
C++
// C++ Program for the above approach#include <bits/stdc++.h>using namespace std;// structure of tree nodestruct Node { int data; struct Node* left; struct Node* right; Node(int data) { this->data = data; this->left = NULL; this->right = NULL; }};// function to find the height of binary treeint height(Node* root){ if (root == NULL) return 0; return max(height(root->left), height(root->right)) + 1;}// Function to print the nodes of a// BST in Top Level Order and Reversed// Bottom Level Order alternativelyvoid printBST(Node* root){ // base cas if (root == NULL) return; vector<vector<int> > ans(height(root)); int level = 0; // initializing the queue for level order traversal queue<Node*> q; q.push(root); while (!q.empty()) { int n = q.size(); for (int i = 0; i < n; i++) { Node* front_node = q.front(); q.pop(); ans[level].push_back(front_node->data); if (front_node->left != NULL) q.push(front_node->left); if (front_node->right != NULL) q.push(front_node->right); } level++; } auto it1 = ans.begin(); auto it2 = ans.end() - 1; while (it1 < it2) { for (int i : *it1) { cout << i << " "; } for (int i = (*it2).size() - 1; i >= 0; i--) { cout << (*it2)[i] << " "; } it1++; it2--; } if (it1 == it2) { for (int i : *it1) { cout << i << " "; } }}// driver code to test above functionint main(){ // creating the binary tree Node* root = new Node(25); root->left = new Node(20); root->right = new Node(36); root->left->left = new Node(10); root->left->right = new Node(22); root->left->left->left = new Node(5); root->left->left->right = new Node(12); root->right->left = new Node(30); root->right->right = new Node(40); root->right->left->left = new Node(28); root->right->right->left = new Node(38); root->right->right->right = new Node(48); printBST(root); return 0;}// THIS CODE IS CONTRIBUTED BY KIRTI// AGARWAL(KIRTIAGARWAL23121999) |
Java
import java.util.*;// structure of tree nodeclass Node { int data; Node left, right; Node(int data) { this.data = data; this.left = null; this.right = null; }}// class to print the nodes of a// BST in Top Level Order and Reversed// Bottom Level Order alternativelyclass Main { // function to find the height of binary tree public static int height(Node root) { if (root == null) return 0; return Math.max(height(root.left), height(root.right)) + 1; } public static void printBST(Node root) { // base case if (root == null) return; List<List<Integer> > ans = new ArrayList<>(); int level = 0; // initializing the queue for level order traversal Queue<Node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { int n = q.size(); List<Integer> currLevel = new ArrayList<>(); for (int i = 0; i < n; i++) { Node front_node = q.poll(); currLevel.add(front_node.data); if (front_node.left != null) q.add(front_node.left); if (front_node.right != null) q.add(front_node.right); } ans.add(currLevel); level++; } int it1 = 0; int it2 = ans.size() - 1; while (it1 < it2) { for (int i : ans.get(it1)) { System.out.print(i + " "); } for (int i = ans.get(it2).size() - 1; i >= 0; i--) { System.out.print(ans.get(it2).get(i) + " "); } it1++; it2--; } if (it1 == it2) { for (int i : ans.get(it1)) { System.out.print(i + " "); } } } // driver code to test above function public static void main(String[] args) { // creating the binary tree Node root = new Node(25); root.left = new Node(20); root.right = new Node(36); root.left.left = new Node(10); root.left.right = new Node(22); root.left.left.left = new Node(5); root.left.left.right = new Node(12); root.right.left = new Node(30); root.right.right = new Node(40); root.right.left.left = new Node(28); root.right.right.left = new Node(38); root.right.right.right = new Node(48); printBST(root); }} |
Javascript
// JavaScript program for the above approach// structure of tree nodeclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}// function to find the height of binary treefunction height(root){ if(root == null) return 0; return Math.max(height(root.left), height(root.right)) + 1;}// function to print the nodes of a// BST in Top level order and reversed// bottom level order alternativelyfunction printBST(root){ // base case if(root == null) return; let ans = []; for(let i = 0; i<height(root); i++){ ans[i] = []; } let level = 0; // initializing the queue for level roder traversal let q = []; q.push(root); while(q.length > 0){ let n = q.length; for(let i = 0; i<n; i++){ let front_node = q.shift(); ans[level].push(front_node.data); if(front_node.left) q.push(front_node.left); if(front_node.right) q.push(front_node.right); } level++; } let it1 = 0; let it2 = ans.length - 1; while(it1 < it2){ for(let i = 0; i<ans[it1].length; i++){ console.log(ans[it1][i] + " "); } for(let i = ans[it2].length -1; i >= 0; i--){ console.log(ans[it2][i] + " "); } it1++; it2--; } if(it1 == it2){ for(let i = 0; i<ans[it1].length; i++){ console.log(ans[it1][i] + " "); } }}// driver program to test above functionlet root = new Node(25);root.left = new Node(20);root.right = new Node(36);root.left.left = new Node(10);root.left.right = new Node(22);root.left.left.left = new Node(5);root.left.left.right = new Node(12);root.right.left = new Node(30);root.right.right = new Node(40);root.right.left.left = new Node(28);root.right.right.left = new Node(38);root.right.right.right = new Node(48);printBST(root);// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Python
# Define the structure of tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# Function to find the height of binary treedef height(root): if root is None: return 0 return max(height(root.left), height(root.right)) + 1# Function to print the nodes of a BST in top-level order and reversed bottom-level order alternativelydef printBST(root): # Base case if root is None: return # Initialize a list of empty lists to store nodes at each level ans = [[] for i in range(height(root))] level = 0 # Intialize the queue for level order traversal q = [] q.append(root) # Traverse the tree in level order and store nodes at each level in the ans list while len(q) > 0: n = len(q) for i in range(n): front_node = q.pop(0) ans[level].append(front_node.data) if front_node.left: q.append(front_node.left) if front_node.right: q.append(front_node.right) level += 1 # Traverse the ans list and print nodes in top-level order and reversed bottom-level order alternatively it1 = 0 it2 = len(ans) - 1 while it1 < it2: # Print nodes in top-level order for i in range(len(ans[it1])): print(ans[it1][i]) # Print nodes in reversed bottom-level order for i in range(len(ans[it2])-1, -1, -1): print(ans[it2][i]) it1 += 1 it2 -= 1 # If there is only one level left, print nodes in top-level order if it1 == it2: for i in range(len(ans[it1])): print(ans[it1][i])# Driver program to test the above functionroot = Node(25)root.left = Node(20)root.right = Node(36)root.left.left = Node(10)root.left.right = Node(22)root.left.left.left = Node(5)root.left.left.right = Node(12)root.right.left = Node(30)root.right.right = Node(40)root.right.left.left = Node(28)root.right.right.left = Node(38)root.right.right.right = Node(48)printBST(root) |
C#
// C# Program for the above approachusing System;using System.Collections.Generic;// structure of tree nodeclass Node { public int data; public Node left, right; public Node(int data) { this.data = data; this.left = null; this.right = null; }}// class to print the nodes of a// BST in Top Level Order and Reversed// Bottom Level Order alternativelyclass MainClass { // function to find the height of binary tree public static int Height(Node root) { if (root == null) return 0; return Math.Max(Height(root.left), Height(root.right)) + 1; } public static void PrintBST(Node root) { // base case if (root == null) return; List<List<int> > ans = new List<List<int> >(); int level = 0; // initializing the queue for level order traversal Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count != 0) { int n = q.Count; List<int> currLevel = new List<int>(); for (int i = 0; i < n; i++) { Node front_node = q.Dequeue(); currLevel.Add(front_node.data); if (front_node.left != null) q.Enqueue(front_node.left); if (front_node.right != null) q.Enqueue(front_node.right); } ans.Add(currLevel); level++; } int it1 = 0; int it2 = ans.Count - 1; while (it1 < it2) { foreach(int i in ans[it1]) { Console.Write(i + " "); } for (int i = ans[it2].Count - 1; i >= 0; i--) { Console.Write(ans[it2][i] + " "); } it1++; it2--; } if (it1 == it2) { foreach(int i in ans[it1]) { Console.Write(i + " "); } } } // driver code to test above function public static void Main() { // creating the binary tree Node root = new Node(25); root.left = new Node(20); root.right = new Node(36); root.left.left = new Node(10); root.left.right = new Node(22); root.left.left.left = new Node(5); root.left.left.right = new Node(12); root.right.left = new Node(30); root.right.right = new Node(40); root.right.left.left = new Node(28); root.right.right.left = new Node(38); root.right.right.right = new Node(48); PrintBST(root); }}// This code is contributed by adityashatmfh |
Output
25 48 38 28 12 5 20 36 40 30 22 10
Time Complexity: O(V) where V is the number of vertices in given binary tree.
Auxiliary Space: O(V) due to queue and vector of ans.
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!
