Binary Search Trees: Given an array, check if it represents inorder traversal of BST.

Problem Statement:

You are given an array, you need to check if can be represented as in order traversal of BST.

BST is a tree that satisfies below condition:

1. Left subtree will have the node less than the node key

2. Right subtree will have the node greater than the node key

3. Duplicate values are not allowed

Example:

Input: arr[] = {1, 2, 3, 4, 5}
Output: Yes

Solution Explanation:

In-order traversal of BST is sorted.
Hence check if the array is sorted or not.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include<iostream> 
#include<vector> 
using namespace std; 


bool solution(vector<int> &arr) {

    int len = arr.size();
  
    if (len == 0 || len == 1)
        return true;

    for (int i = 1; i < len; i++)
    {
        if (arr[i-1] > arr[i])
            return false;
    }

    return true;
}

int main() {
    vector<int> arr = { 1, 2, 3, 4, 5 };
    
    if (solution(arr))
        cout << "True";
    else
        cout << "False";
        
  return 0;
}

Output

True