1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Code in C++
4.
4.1.
What is a BST (Binary Search Tree)?
4.2.
What is an Inorder Traversal?
5.
Conclusion
Last Updated: Mar 27, 2024

# Traverse a BST in a Min-Max Manner

Gaurish Anand
0 upvote

## Introduction

Binary Trees are popular Data Structures and have a wide range of applications throughout various fields. Binary Trees are also important when it comes to interviews with top tech companies. A mastery of Binary Trees could help us solve a lot of problems. In this article, we are going to take a look at one such problem.

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 -

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.

Check out this problem - Diameter Of Binary Tree

### 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.

### What is an Inorder Traversal?

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

## Conclusion

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.