Search in a binary search tree

Tree Binary Search Tree Binary Tree

82.5% acceptance

Feb 20, 2026

6545

218

Given the root of a BST and an integer val, find the node with that value and return the subtree rooted at it. Return null if not found.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

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