Print nodes of a Binary Search Tree in Top Level Order and Reversed Bottom Level Order alternately

Gaurish Anand
Last Updated: May 13, 2022

Introduction

Before beginning with this question, let’s recap what a BST is and the level order traversal of a binary tree. 

BST is a unique binary tree where each node contains a value greater than all the values present in the left subtree and smaller than or equal to the values present in the right subtree. 

Example - 

 

Source

 

Level Order Traversal of a Binary Tree means traversing the tree level-wise i.e first travel all the nodes at the 1st level, then 2nd level, so on. 

Level Order Traversal of the above Binary Search Tree is: 30 20 39 10 25 35 42 15 23  

We can traverse level-wise in a tree using queues. For further reference, check this article

Problem Statement

You are given a Binary Search Tree (BST) where you have to print the nodes in the following manner: 

  1. First, print the 1st level, then Nth level, then 2nd level, (N-1)th level, and so on.
  2. The levels from the top should be printed from left to right, and levels from the bottom should be printed from right to left.


Example: 

Output for the above tree will be: 30 23 15 20 39 42 35 25 10

Approach

  1. 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.
     
  2. 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.
     
  3. Then do j-- and i++.
     
  4. 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

  1. 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.
     
  2. 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.

Key Takeaways

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.

Since Binary Search Tree is frequently asked in interviews, we recommend you practice more problems based on Binary Search Trees on CodeStudio. 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think