Validate binary search tree

Tree Depth-First Search Binary Search Tree Binary Tree

35.4% acceptance

Feb 27, 2026

18273

1448

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys strictly less than the node's key. The right subtree of a node contains only nodes with keys strictly greater than the node's key. Both the left and right subtrees must also be binary search trees.

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 is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    Self::validate(root.as_ref(), None, None)
  }
  
  fn validate(node: Option<&Rc<RefCell<TreeNode>>>, min: Option<i32>, max: Option<i32>) -> bool {
    if let Some(n) = node {
      let n = n.borrow();
      if let Some(min_val) = min {
        if n.val <= min_val {
          return false;
        }
      }
      if let Some(max_val) = max {
        if n.val >= max_val {
          return false;
        }
      }
      Self::validate(n.left.as_ref(), min, Some(n.val)) && 
      Self::validate(n.right.as_ref(), Some(n.val), max)
    } else {
      true
    }
  }
}