Traverse a BST in a min-max manner

Gaurish Anand
Last Updated: May 13, 2022

Introduction

Before beginning with this question, let’s recap what a BST is and how to do an inorder 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

Inorder Traversal of a Binary Tree means first traversing the left subtree, root, and right subtree. 

For example : 

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

Problem Statement

You are given a Binary Search Tree (BST). You have to traverse the tree in a min-max manner, i.e., first, travel the minimum of the tree, then maximum and then 2nd minimum, 2nd maximum, and so on. 

Example: For the above tree output should be

10 42 15 39 20 35 23 30 25 

Approach 

We can see that the inorder traversal is traversing a BST in a sorted manner. After finding the inorder traversal of a BST and storing it in the array, we can easily print the array in a min-max manner from both ends using a two-pointer approach. 

  1. First, store the inorder traversal of the binary tree in an array. 
     
  2. Now since the array is sorted , make 2 pointers i = 0 , j = n-1.
     
  3. i will traverse from the start of the array, i.e., will travel on the minimum, and j will traverse from the end of the array, i.e., will travel on the maximum.
     
  4. Now run a loop till all the elements are printed. In each loop (run) print array[i] and array[j]. After printing, increment i by 1 and decrement j by 1 (Now i and j will point to the next minimum and next maximum respectively in the array).

Dry run on Inorder Traversal

Inorder Traversal = [10 15 20 23 25 30 35 39 42]


  1. inorderTraversal = [10 15 20 23 25 30 35 39 42]
                              
    i = 0
    j = n-1 = 9-1 = 8
    Print inorderTraversal[i]  & inorderTraversal[j] , then do  i++ , j--
     

  2. inorderTraversal = [10 15 20 23 25 30 35 39 42]
                                       
    i = 1
    j = 7
    Print inorderTraversal[i]  & inorderTraversal[j] , then do  i++ , j--
     

  3. inorderTraversal = [10 15 20 23 25 30 35 39 42]
                                           
    i = 2
    j = 6
    Print inorderTraversal[i]  & inorderTraversal[j] , then do  i++ , j--
     

  4. inorderTraversal = [10 15 20 23 25 30 35 39 42]
                                                 
    i = 3
    j = 5
    Print inorderTraversal[i]  & inorderTraversal[j] , then do  i++ , j--
     

  5. inorderTraversal = [10 15 20 23 25 30 35 39 42]
                                                           
    i = 4
    j = 4
    Since i == j, therefore print  inorderTraversal[i] , i++ , j--
     

Since i > j, therefore the loop should break.

Code in C++

#include<iostream>
#include<vector>
using namespace std;
class TreeNode{
	public:
	int value;
	TreeNode *left , *right;
	TreeNode(int value){
		this->value = value;
		left = NULL;
		right = NULL;
	}
};

// storing inOrder Traversal of the tree in an array
void inOrderTraversal(TreeNode* root , vector<int>& inorder){
	if(root==NULL){
		return;
	}
	// first travel the tree on left
	inOrderTraversal(root->left,inorder);

	// Then travel on the current node
	inorder.push_back(root->value);

	// At last travel the tree on right
	inOrderTraversal(root->right,inorder);
}

int main(){

	// 	    INPUT TREE
	//          30
	//        /     \
	//      20       39
	//      /  \    /  \
	//    10    25 35  42
	//      \   /
	//      15  23

	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);

	vector<int> inorder;
	inOrderTraversal(root,inorder);

	// Now since traversing a BST , we will have all the elements in sorted order in our tree
	// Therefore using 2 pointers we will print the tree in min-max manner
	int i = 0;
	int j = inorder.size()-1;
	while(i<=j){
		if(i!=j){
			cout<<inorder[i]<<" "<<inorder[j]<<" ";
		}else{
			// This condition can be achieved when we have odd number of elements.
			cout<<inorder[i]<<" ";
		}
		i++;
		j--;
	}
} 

 

Output:

The nodes for this binary tree in a min-max manner are :
10 42 15 39 20 35 23 30 25 

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

Since we are storing the tree in an array to traverse it later in a min-max manner, space complexity is O(n), where n = Total number of nodes in a tree.

 

Frequently Asked Questions

Q1. What is a BST (Binary Search Tree)?

BST is a binary tree in which every node of the tree should satisfy these 2 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.

 

Q2. What is an Inorder Traversal?

In the inorder traversal of a binary tree, we first traverse the whole left subtree, root, and right subtree. 

Key Takeaways

This article taught us how to do an Inorder Traversal in a binary tree with all the essential concepts. We also learned to traverse the tree in a min-max manner using a two-pointer approach. 

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