# Question

Formatted question description: https://leetcode.ca/all/255.html

 255 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.

Consider the following binary search tree:

5
/ \
2   6
/ \
1   3

Example 1:

Input: [5,2,6,1,3]
Output: false

Example 2:

Input: [5,2,1,3,6]
Output: true

Could you do it using only constant space complexity?

@tag-tree


# Algorithm

First set a minimum value low, then traverse the array, if the current value is less than the minimum value low, return false.

For the root node, push it onto the stack, and then traverse back,

If the number encountered is smaller than the element at the top of the stack, it means that it is the point of its left subtree and continues to be pushed onto the stack.

Until the number encountered is greater than the top element of the stack, then it is the value on the right child. You need to find the right subtree of which node,

So update the low value and delete the top element of the stack, and then continue to compare with the next top element,

If it is still greater than, continue to update the low value and delete the top of the stack, until the stack is empty or the current stack top element is greater than the current value, stop, push the current value,

In this way, if it does not return false before traversing the entire array, return true at the end.

Java