Trim a binary search tree

Tree Depth-First Search Binary Search Tree Binary Tree

66.6% acceptance

Feb 20, 2026

6084

265

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its values are in [low, high].

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn trim_bst(
    root: Option<Rc<RefCell<TreeNode>>>,
    low: i32,
    high: i32,
  ) -> Option<Rc<RefCell<TreeNode>>> {
    match root {
      None => None,
      Some(n) => {
        let val = n.borrow().val;
        if val < low {
          Solution::trim_bst(n.borrow().right.clone(), low, high)
        } else if val > high {
          Solution::trim_bst(n.borrow().left.clone(), low, high)
        } else {
          let left = n.borrow().left.clone();
          let right = n.borrow().right.clone();
          n.borrow_mut().left = Solution::trim_bst(left, low, high);
          n.borrow_mut().right = Solution::trim_bst(right, low, high);
          Some(n)
        }
      }
    }
  }
}