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.

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

Solution

public class Solution {
     public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) return true;
        return helper(preorder, 0, preorder.length - 1);
    }

    private boolean helper(int[] preOrder, int left, int right) {
        if (left >= right) return true;
        else {
            int pivot = preOrder[left];
            int bigger = -1;

            for (int i = left + 1; i <= right; i++) {
                if (bigger == -1 && preOrder[i] > pivot) bigger = i;
                if (bigger != -1 && preOrder[i] < pivot) return false;
            }

            if (bigger == -1) {
                return helper(preOrder, left + 1, right);
            } else {
                return helper(preOrder, left + 1, bigger - 1) && helper(preOrder, bigger, right);
            }

        }
    }
}