Description
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
Examples
Input:
preorder = [5,2,1,3,6]Output:
trueExplanation:
Valid BST preorder.
Input:
preorder = [5,2,6,1,3]Output:
falseExplanation:
For preorder = [5,2,6,1,3], the answer is false because the verify preorder sequence in bst condition is not met.
Input:
preorder = [10,5,1,7,40,30]Output:
trueExplanation:
This is a valid BST preorder traversal. Starting with root 10, going left to subtree with root 5 (5 < 10), then to 1 (1 < 5), then to 7 (7 > 5 but < 10). After exhausting the left subtree of 10, moving to the right subtree with root 40 (40 > 10), then to 30 (30 < 40 but > 10). All nodes maintain BST property relative to their ancestors.
Constraints
- •
1 ≤ preorder.length ≤ 10⁴