Construct binary search tree from preorder traversal

Array Stack Tree Binary Search Tree Monotonic Stack Binary Tree

84.1% acceptance

Feb 27, 2026

6740

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root. It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases. A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val. A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn bst_from_preorder(preorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
    fn build(pre: &[i32], min: i32, max: i32, idx: &mut usize) -> Option<Rc<RefCell<TreeNode>>> {
      if *idx >= pre.len() || pre[*idx] < min || pre[*idx] > max { return None; }
      let val = pre[*idx]; *idx += 1;
      let node = Rc::new(RefCell::new(TreeNode::new(val)));
      node.borrow_mut().left = build(pre, min, val - 1, idx);
      node.borrow_mut().right = build(pre, val + 1, max, idx);
      Some(node)
    }
    build(&preorder, i32::MIN, i32::MAX, &mut 0)
  }
}