Range sum of bst

Tree Depth-First Search Binary Search Tree Binary Tree

87.6% acceptance

Feb 25, 2026

7236

389

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

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 range_sum_bst(root: Option<Rc<RefCell<TreeNode>>>, low: i32, high: i32) -> i32 {
    match root {
      None => 0,
      Some(node) => {
        let n = node.borrow();
        let mut sum = 0;
        if n.val >= low && n.val <= high { sum += n.val; }
        if n.val > low { sum += Self::range_sum_bst(n.left.clone(), low, high); }
        if n.val < high { sum += Self::range_sum_bst(n.right.clone(), low, high); }
        sum
      }
    }
  }
}