LeetCode 255: Verify Preorder Sequence in Binary Search Tree

Explanation:

The problem asks us to determine if a given array represents the preorder traversal of a valid binary search tree (BST).

To solve this problem, we can use a stack to simulate the traversal of the BST. We iterate through the array and keep track of the nodes that we have seen so far. If we encounter a node greater than the previous node, we know that we have entered the right subtree of some node. We then pop all the nodes from the stack that are smaller than the current node because all the nodes in the left subtree have already been visited.

At the end, if we have correctly traversed the entire array without violating the BST property, then the array represents the preorder traversal of a valid BST.

: :

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> stack = new Stack<>();
        int low = Integer.MIN_VALUE;
        for (int num : preorder) {
            if (num < low) {
                return false;
            }
            while (!stack.isEmpty() && num > stack.peek()) {
                low = stack.pop();
            }
            stack.push(num);
        }
        return true;
    }
}