Traverse a BST in a Min-Max Manner

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

You can also try this code with Online C++ Compiler

Run Code

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

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

Recommended Reading:

• Difference Between Binary Tree and Binary Search Tree
• Median of all Nodes From A Given Range in BST
• Print All Odd Nodes of the Binary Search Tree
• Print All Even Nodes of the Binary Search Tree
• Count  Permutations of the Given Array that Generates The Same Binary Search Tree
• Level Order Traversal in Spiral Form
• Level Order Traversal By Line
• Level Order Traversal With Direction Change After Every Two Levels
• Specific Level Order Traversal of Binary Tree

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