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.

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

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        return helper(preorder, 0, preorder.length - 1);
    }

    private boolean helper(int[] preorder, int start, int end){
        if (start > end) return true;

        int root = preorder[start], i = start + 1;
        for (; i <= end; i++){
            if (root < preorder[i]) break;
        }

        for (int j = i; j <= end; j++){
            if (root > preorder[j]) return false;
        }

        return helper(preorder, start + 1, i - 1) && helper(preorder, i, end);
    }
}

class Solution {
    int index = 0;
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 2) return true;

        return dfs(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean dfs(int[] preorder, int min, int max){
        if (index >= preorder.length || preorder[index] > max) return true;

        int root = preorder[index++];
        if (root < min) return false;

        return dfs(preorder, min, root) && dfs(preorder, root, max);
    }
}