#include <bits/stdc++.h>
using namespace std;

// function which returns true if it's a valid inorder
// traversal for a BST, else return false
int isInorderTraversal(vector<int> a, int n)
{
    // base case, a NULL tree or a single node is always a BST
    if (n == 0 || n == 1)
        return true;
    // check if it's a sorted list(strictly increasing only)
    for (int i = 0; i < n - 1; i++)
    {
        if (a[i] >= a[i + 1])
            return false;
    }

    return true;
}

int main()
{
    int t, n, item;

    cout << "Enter size of the list" << endl;
    cin >> n;

    cout << "Enter the elements" << endl;

    vector<int> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    bool result = isInorderTraversal(arr, n);

    if (result)
        cout << "This array is a valid inorder traversal for a BST" << endl;
    else
        cout << "This array is an invalid inorder traversal for a BST" << endl;

    return 0;
}


Output


Enter size of the list
5
Enter the elements
1 2 3 4 5
This array is a valid inorder traversal for a BST