Valid BST from Preorder

• Time : $O(n)$
• Space : $O(1)$

bool dfs(vector<int>& A, int& p, int mi, int ma) {
    if(p == A.size()) return true;
    if(A[p] < mi or A[p] > ma) return false;
    int now = p;
    bool res = true;
    if(p + 1 < A.size() and A[now] > A[p+1] and A[p+1] >= mi) res = dfs(A,++p,mi,A[now] - 1);
    if(res and p + 1 < A.size() and A[now] < A[p+1] and A[p+1] <= ma) res = dfs(A,++p,A[now] + 1, ma);
    return res;
}

int Solution::solve(vector<int> &A) {
    int p = 0;
    return dfs(A,p,INT_MIN,INT_MAX) and p + 1 == A.size();
}