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

int nextgreaterOfRoot(vector<int> &arr, int l, int r, int key)
{
    for (int i = l; i <= r; i++)
        if (arr[i] > key)
            return i;

    return r + 1;
}

bool validPreorderRecur(vector<int> &arr, int left, int right)
{
    // base case
    // NULL is a valid BST
    if (left > right)
        return true;

    int j = nextgreaterOfRoot(arr, left + 1, right, arr[left]);
    int root = arr[left];
    /*
    if any element after the next greater element of the root
    is less than the root value
    then it can't be a valid preorder traversal as the part
    starting from the next greater element of the root
    should fall in right subtree only
    */
    for (int i = j + 1; i <= right; i++)
        if (arr[i] <= root)
            return false;

    /*
    recur for left subtree & right subtree
    if both is true then it's true else false
    left subtree -> arr[left+1,j-1]
    right subtree-> arr[left+1,j-1]
    */
    return validPreorderRecur(arr, left + 1, j - 1) && validPreorderRecur(arr, j, right);
}

bool validPreorder(vector<int> &arr)
{
    if (arr.size() == 0)
        return false;

    return validPreorderRecur(arr, 0, arr.size() - 1);
}

int main()
{
    vector<int> preorder1{16, 3, 13, 10, 20, 18};
    vector<int> preorder2{16, 3, 13, 10, 20, 15};

    ///////// checking whther the first preorder traversal is valid or not
    cout << "Checking the first array\n";
    bool isValidPreOrder = validPreorder(preorder1);
    if (isValidPreOrder)
        cout << "The given array is valid preorder traversal\n";
    else
        cout << "The given array is not valid preorder traversal\n";

    ///////// checking whther the second preorder traversal is valid or not
    cout << "Checking the second array\n";
    isValidPreOrder = validPreorder(preorder2);
    if (isValidPreOrder)
        cout << "The given array is a valid preorder traversal\n";
    else
        cout << "The given array is not valid preorder traversal\n";

    return 0;
}

Output

Checking the first array
The given array is valid preorder traversal
Checking the second array
The given array is not valid preorder traversal