C++, O(n), Recursive, 5 lines

#1 
int solver(vector<int> &A, int &indx, int L, int R){
   if (indx >= A.size()) return 1;
   if( !(L<A[indx] && A[indx]<=R) ) return 0;  // check if root satisfies the condtn

   int end = A[indx];
   solver(A,++indx,L,end); //go left
   return solver(A,indx,end,R); // go right        }

initially L = -INT_MAX, R=INT_MAX, indx = 0