## 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?

## Rust Solution

``````struct Solution;

impl Solution {
fn verify_preorder(preorder: Vec<i32>) -> bool {
let mut low = std::i32::MIN;
let mut stack: Vec<i32> = vec![];
for x in preorder {
if x < low {
return false;
}
while let Some(&top) = stack.last() {
if top < x {
stack.pop();
low = top;
} else {
break;
}
}
stack.push(x);
}
true
}
}

#[test]
fn test() {
let preorder = vec![5, 2, 6, 1, 3];
let res = false;
assert_eq!(Solution::verify_preorder(preorder), res);
let preorder = vec![5, 2, 1, 3, 6];
let res = true;
assert_eq!(Solution::verify_preorder(preorder), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.