Verify preorder sequence in binary search tree

Array Stack Tree Binary Search Tree Recursion Monotonic Stack Binary Tree

51.7% acceptance

Mar 31, 2026

1267

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

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn verify_preorder(preorder: Vec<i32>) -> bool {
    let mut stack: Vec<i32> = Vec::new();
    let mut lower_bound = i32::MIN;
    for &val in &preorder {
      if val < lower_bound {
        return false;
      }
      while let Some(&top) = stack.last() {
        if top >= val { break; }
        lower_bound = stack.pop().unwrap();
      }
      stack.push(val);
    }
    true
  }
}