Cacher is the code snippet organizer for pro developers

public class Solution {
    private boolean helper(int[] preorder, int start, int end) {
        if (start >= end) return true;
        int root = preorder[start];
        int split = -1;
        for (int i = start + 1; i <= end; i++) {
            if (split == -1 && preorder[i] > root) split = i;
            if (split != - 1 && preorder[i] < root) return false;
        }
        if (split == -1) {
            return helper(preorder, start + 1, end);
        } else {
            return helper(preorder, start + 1, split - 1) && helper(preorder, split, end);
        }
    }
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length < 2) return true;
        return helper(preorder, 0, preorder.length - 1);
    }
}

/*
Solution 1
Kinda simulate the traversal, keeping a stack of nodes (just their values) of which we're still in the left subtree. 
If the next number is smaller than the last stack value, then we're still in the left subtree of all stack nodes, 
so just push the new one onto the stack. 
But before that, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, 
in the right subtree of an ancestor). Also, use the popped values as a lower bound, 
since being in their right subtree means we must never come across a smaller number anymore.
*/
public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE;
    Stack<Integer> path = new Stack();
    for (int p : preorder) {
        if (p < low)
            return false;
        while (!path.empty() && p > path.peek())
            low = path.pop();
        path.push(p);
    }
    return true;
}

/*Same as above, but abusing the given array for the stack.*/
public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE, i = -1;
    for (int p : preorder) {
        if (p < low)
            return false;
        while (i >= 0 && p > preorder[i])
            low = preorder[i--];
        preorder[++i] = p;
    }
    return true;
}