255. Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Consider the following binary search tree:

     5
    / \
   2   6
  / \
 1   3

Example 1:

Input: [5,2,6,1,3]
Output: false

Example 2:

Input: [5,2,1,3,6]
Output: true

Follow up: Could you do it using only constant space complexity?

// Stack (simulate preorder traversal)
bool verifyPreorder(vector<int>& preorder) { // time: O(n); space: O(n)
    int low = INT_MIN;
    stack<int> st;
    for (int cur : preorder) {
        if (cur < low) return false;
        while (!st.empty() && cur > st.top()) {
            low = st.top(); st.pop();
        }
        st.push(cur);
    }
    return true;
}

// Constant space but abuse the input array
bool verifyPreorder(vector<int>& preorder) { // time: O(n); space: O(1)
    int low = INT_MIN, idx = -1;
    for (int cur : preorder) {
        if (cur < low) return false;
        while (idx >= 0 && preorder[idx] < cur) {
            low = preorder[idx--];
        }
        preorder[++idx] = cur;
    }
    return true;
}

// Divide and Conquer
bool helper(vector<int>& preorder, int start, int end, int lower, int upper) {
    if (start > end) return true;
    int val = preorder[start], i;
    if (val <= lower || val >= upper) return false;
    for (i = start + 1; i <= end; ++i) {
        if (preorder[i] >= val) break;
    }
    return helper(preorder, start + 1, i - 1, lower, val) && helper(preorder, i, end, val, upper);
}
bool verifyPreorder(vector<int>& preorder) { // time: O(n^2); space: O(n)
    return helper(preorder, 0, preorder.size() - 1, INT_MIN, INT_MAX);
}