Approach

Store the level order traversal of the BST in a 2D vector.
For storing the level order traversal, we can push an extra value = NULL at the end of each level. Whenever we encounter a null, we get to know that we have traversed a level, and from now on, we will be traversing the nodes of the next level in the queue.

We can print the 2D vector alternately from top and bottom using 2 pointers, i and j, i points to a level at the top, and j points to a level at the bottom. Traverse the ith row from left to right and jth row from right to left.

Then do j and i++.
 Repeat Step 2 until j>i.
Code in C++
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
class TreeNode{
public:
int value;
TreeNode *left , *right;
TreeNode(int value){
this>value = value;
left = NULL;
right = NULL;
}
};
vector<vector<int> > getLevelOrderTraversal(TreeNode* root){
vector<vector<int> > ans;
// This will store values of nodes for the level which we are currently traversing
vector<int> currentLevel;
// 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;
q.push(root);
q.push(NULL);
while(q.size()>1){
TreeNode* currentNode = q.front();
q.pop();
if(currentNode==NULL){
ans.push_back(currentLevel);
currentLevel.clear();
if(q.size()==0){
// It means no more level to be traversed
return ans;
}else{
q.push(NULL);
}
}else{
currentLevel.push_back(currentNode>value);
if(currentNode>left!=NULL){
q.push(currentNode>left);
}
if(currentNode>right!=NULL){
q.push(currentNode>right);
}
}
}
ans.push_back(currentLevel);
return ans;
}
int main(){
// INPUT TREE
// 30
// / \
// 20 39
// / \ / \
// 10 25 35 42
// \ / \
// 15 23 37
TreeNode* root = new TreeNode(30);
root>left = new TreeNode(20);
root>right = new TreeNode(39);
root>left>left = new TreeNode(10);
root>left>right = new TreeNode(25);
root>right>left = new TreeNode(35);
root>right>right = new TreeNode(42);
root>left>left>right = new TreeNode(15);
root>left>right>left = new TreeNode(23);
root>right>left>right = new TreeNode(37);
// Getting the value of nodes level wise
vector<vector<int> > levelOrderTraversal = getLevelOrderTraversal(root);
// Now traversing the tree alternatively from top and bottom using 2 pointers
int i = 0;
int j = levelOrderTraversal.size()1;
while(i<=j){
if(i!=j){
for(int k=0;k<levelOrderTraversal[i].size();k++){
cout<<levelOrderTraversal[i][k]<<" ";
}
for(int k=levelOrderTraversal[j].size()1;k>=0;k){
cout<<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].size();k++){
cout<<levelOrderTraversal[i][k]<<" ";
}
}
i++;
j;
}
}
Output
30 37 23 15 20 39 42 35 25 10
Time Complexity
Since we traverse the whole tree only once, T(n) = O(n), where n = the total number of nodes in a tree.
Space Complexity
We store all the nodes in a 2D array to traverse them later. Therefore space complexity is O(n), where n = Total number of nodes in a tree.
Frequently Asked Questions
What is a BST (Binary Search Tree)?
BST is a binary tree in which every node of the tree should satisfy these two properties:
1) All the nodes in the left subtree should have lesser values than the value at the current node.
2) All the nodes in the right subtree should have values that are either equal to or more than the value at the current node.
How to store a level order traversal in an array?
It is similar to traversing level order traversal only. We can push an extra value = NULL at the end of each level.
Whenever we encounter a null, we get to know that we have traversed a level, and from now on, we will be traversing the nodes on the next level in the queue.
Conclusion
This article taught us how to store Binary Tree Level Order Traversal values with all the essential concepts. We also learned how to alternately print the nodes of a BST from top and bottom.
Recommended Reading:
Since Binary Search Tree is frequently asked in interviews, we recommend you practice more problems based on Binary Search Trees on Coding Ninjas Studio.
Recommended Problems: