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: 

1
2
3
4
5
    5
   / \
  2   6
 / \
1   3

Example1:

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

Example2:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int low = Integer.MIN_VALUE;
        Stack<Integer> st = new Stack<>();
        for (int p : preorder) {
            if (p < low) return false;
            while (!st.empty() && p > st.peek()) {
                low = st.pop();   
            }
            st.push(p);
        }
        return true;
    }
}
  1. stack: find global min, then bigger: later value1 vs before value backwards: stack.
  2. while: pop ALL stack values smaller than p; i.e. p is the right child node now, pop all left/root nodes, until this “right node” becomes on the left children chain of ONE node. Then, “big-smallest-big” pattern again.
  3. when while finishes, there is no node left or root to p, i.e. p is global min again.
  4. so p must be smallest. Any low larger than p would indicate this is not preorder.
  5. If use an array, anchored at smallest value index, then compare values going towards 2 directions: not good, because if fact, that’s comparing just 2 children nodes, left and right. BUT, it is unknown which node is strictly the parent node of this right node. As a result, all nodes left/parent to this right node should be compared. In that case, a stack and while loop would be the best option.