Delete node in a bst

Tree Binary Search Tree Binary Tree

54.2% acceptance

Jan 13, 2026

10355

383

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages: Search for a node to remove. If the node is found, delete the node.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn delete_node(root: Option<Rc<RefCell<TreeNode>>>, key: i32) -> Option<Rc<RefCell<TreeNode>>> {
    if let Some(node) = root {
      let node_val = node.borrow().val;
      if key < node_val {
        let left = node.borrow().left.clone();
        node.borrow_mut().left = Self::delete_node(left, key);
        Some(node)
      } else if key > node_val {
        let right = node.borrow().right.clone();
        node.borrow_mut().right = Self::delete_node(right, key);
        Some(node)
      } else {
        // Found the node to delete
        let left = node.borrow().left.clone();
        let right = node.borrow().right.clone();
        
        if left.is_none() {
          return right;
        }
        if right.is_none() {
          return left;
        }
        
        // Node has two children, find minimum in right subtree
        let min_node = Self::find_min(&right);
        node.borrow_mut().val = min_node;
        let right_subtree = node.borrow().right.clone();
        node.borrow_mut().right = Self::delete_node(right_subtree, min_node);
        Some(node)
      }
    } else {
      None
    }
  }
  
  fn find_min(node: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
    if let Some(n) = node {
      let left = n.borrow().left.clone();
      if left.is_none() {
        n.borrow().val
      } else {
        Self::find_min(&left)
      }
    } else {
      0
    }
  }
}