# 255 Verify Preorder Sequence in Binary Search Tree

Given an array of unique integers `preorder`, return `true` if it is the correct preorder traversal sequence of a binary search tree.

Example 1:

``````    5
/ \
2   6
/ \
1   3

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

Example 2:

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

Constraints:

• `1 <= preorder.length <= 104`
• `1 <= preorder[i] <= 104`
• All the elements of `preorder` are unique.

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

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 `````` ``````class Solution: def verifyPreorder(self, preorder: List[int]) -> bool: stack = [] low = -math.inf for num in preorder: if num < low: return False while stack and num > stack[-1]: low = stack.pop() stack.append(num) return True ''' O(1) space Use the preoder list as the stack ''' class Solution: def verifyPreorder(self, preorder: List[int]) -> bool: i = 0 low = -math.inf for num in preorder: if num < low: return False while i > 0 and num > preorder[i - 1]: low = preorder[i - 1] i -= 1 preorder[i] = num i += 1 return True``````