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

Follow up:
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.