LeetCode : 255. Verify Preorder Sequence in Binary Search Tree

[congr]

https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/description/

[congr]

O(N) time, constant space

[congr]

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> stack = new Stack();
        int min = Integer.MIN_VALUE;

        // pop order is inorder (sorted)
        for(int p : preorder) {
            if (min > p) return false;
            while (!stack.isEmpty() && p > stack.peek()) 
                min = stack.pop(); // !!! smaller value should pop first

            stack.push(p);
        }

        return true;
    }
}

[congr]

https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/discuss/68142/Java-O(n)-and-O(1)-extra-space