# 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?

```cpp
// 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;
}
```

```cpp
// 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;
}
```

```cpp
// 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);
}
```