BST Delete Operation in DSA Rust

Mental Model

To remove a value from a binary search tree, we find the node and adjust the tree so it stays sorted and connected.

Analogy: Imagine removing a book from a sorted shelf. If the book is alone, just take it out. If it has neighbors, shift or replace it so the order stays perfect.

    5
   / \
  3   7
 / \   \
2   4   8
↑root

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, delete value 3

Goal: Remove node with value 3 and keep BST properties intact

Step 1: Find node with value 3 starting from root

    5
   / \
  [3] 7
 / \   \
2   4   8

Why: We must locate the node to delete it

Step 2: Node 3 has two children, find its inorder successor (smallest in right subtree), which is 4

    5
   / \
  3   7
 / \   \
2  [4]  8

Why: Replacing with inorder successor keeps BST order

Step 3: Replace node 3's value with 4

    5
   / \
  4   7
 / \   \
2   4   8

Why: We keep the tree connected and sorted by swapping values

Step 4: Delete the original node with value 4 (inorder successor), which has no left child

    5
   / \
  4   7
 /     \
2       8

Why: Remove duplicate value and maintain BST structure

Result:

    5
   / \
  4   7
 /     \
2       8

Annotated Code

DSA Rust

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Rc<RefCell<TreeNode>> {
        Rc::new(RefCell::new(TreeNode { val, left: None, right: None }))
    }
}

fn delete_node(root: Option<Rc<RefCell<TreeNode>>>, key: i32) -> Option<Rc<RefCell<TreeNode>>> {
    if root.is_none() {
        return None;
    }
    let root_rc = root.unwrap();
    let mut root_ref = root_rc.borrow_mut();

    if key < root_ref.val {
        // go left
        let left = root_ref.left.take();
        root_ref.left = delete_node(left, key);
        return Some(root_rc.clone());
    } else if key > root_ref.val {
        // go right
        let right = root_ref.right.take();
        root_ref.right = delete_node(right, key);
        return Some(root_rc.clone());
    } else {
        // found node to delete
        if root_ref.left.is_none() {
            return root_ref.right.clone();
        } else if root_ref.right.is_none() {
            return root_ref.left.clone();
        } else {
            // two children: find inorder successor
            let mut successor = root_ref.right.clone().unwrap();
            while successor.borrow().left.is_some() {
                let left = successor.borrow().left.clone().unwrap();
                successor = left;
            }
            // replace value
            root_ref.val = successor.borrow().val;
            // delete successor node
            let right = root_ref.right.take();
            root_ref.right = delete_node(right, root_ref.val);
            return Some(root_rc.clone());
        }
    }
}

fn print_bst(root: &Option<Rc<RefCell<TreeNode>>>) {
    fn helper(node: &Option<Rc<RefCell<TreeNode>>>, prefix: String, is_left: bool) {
        if let Some(n) = node {
            println!("{}{}{}", prefix, if is_left {"├── "} else {"└── "}, n.borrow().val);
            let new_prefix = prefix.clone() + if is_left {"│   "} else {"    "};
            helper(&n.borrow().left, new_prefix.clone(), true);
            helper(&n.borrow().right, new_prefix, false);
        }
    }
    helper(root, String::new(), false);
}

fn main() {
    // Build tree: 5,3,7,2,4,8
    let root = Some(TreeNode::new(5));
    {
        let r = root.as_ref().unwrap();
        r.borrow_mut().left = Some(TreeNode::new(3));
        r.borrow_mut().right = Some(TreeNode::new(7));
    }
    {
        let left = root.as_ref().unwrap().borrow().left.clone().unwrap();
        left.borrow_mut().left = Some(TreeNode::new(2));
        left.borrow_mut().right = Some(TreeNode::new(4));
    }
    {
        let right = root.as_ref().unwrap().borrow().right.clone().unwrap();
        right.borrow_mut().right = Some(TreeNode::new(8));
    }

    println!("Original BST:");
    print_bst(&root);

    let root = delete_node(root, 3);

    println!("\nBST after deleting 3:");
    print_bst(&root);
}

if root.is_none() { return None; }

handle empty subtree base case

if key < root_ref.val { root_ref.left = delete_node(root_ref.left.take(), key); return Some(root_rc.clone()); }

recurse left if key smaller

else if key > root_ref.val { root_ref.right = delete_node(root_ref.right.take(), key); return Some(root_rc.clone()); }

recurse right if key larger

if root_ref.left.is_none() { return root_ref.right.clone(); } else if root_ref.right.is_none() { return root_ref.left.clone(); }

delete node with zero or one child by returning child

let mut successor = root_ref.right.clone().unwrap(); while successor.borrow().left.is_some() { successor = successor.borrow().left.clone().unwrap(); }

find inorder successor (smallest in right subtree)

root_ref.val = successor.borrow().val;

replace node value with successor value

root_ref.right = delete_node(root_ref.right.take(), root_ref.val);

delete successor node recursively

Output

Original BST:

└── 5

    ├── 3

    │   ├── 2

    │   └── 4

    └── 7

        └── 8



BST after deleting 3:

└── 5

    ├── 4

    │   ├── 2

    └── 7

        └── 8

Complexity Analysis

Time: O(h) where h is tree height because we traverse from root down to the node to delete

Space: O(h) due to recursion stack in worst case of unbalanced tree

vs Alternative: Compared to array deletion which may require shifting O(n), BST deletion is faster for balanced trees with O(log n) height

Edge Cases

Deleting from empty tree

Returns None immediately, no error

DSA Rust

if root.is_none() { return None; }

Deleting leaf node (no children)

Node is simply removed by returning None

DSA Rust

if root_ref.left.is_none() { return root_ref.right.clone(); } else if root_ref.right.is_none() { return root_ref.left.clone(); }

Deleting node with one child

Node replaced by its single child

DSA Rust

if root_ref.left.is_none() { return root_ref.right.clone(); } else if root_ref.right.is_none() { return root_ref.left.clone(); }

When to Use This Pattern

When you need to remove a value from a BST and keep it sorted, use the BST delete pattern because it handles all child cases and preserves order.

Common Mistakes

Mistake: Not handling the two-children case by replacing with inorder successor
Fix: Find the smallest node in right subtree and replace the target node's value with it, then delete that successor node

Mistake: Not reconnecting child nodes properly after deletion
Fix: Return the correct child subtree after deletion to maintain tree links

Summary

Deletes a node from a BST while keeping the tree sorted and connected.

Use when you want to remove a value from a BST without breaking its order.

The key is to replace a node with two children by its inorder successor to keep the BST valid.

Practice

1. What happens when you delete a leaf node (a node with no children) from a Binary Search Tree (BST)?

easy

A. The entire tree is rebuilt from scratch.

B. The node's children replace it in the tree.

C. The node is simply removed with no further changes needed.

D. The tree becomes unbalanced and must be rebalanced immediately.

Solution

1. Step 1: Understand leaf node deletion

   A leaf node has no children, so removing it does not affect other nodes.

2. Step 2: Effect on BST structure

   Since no children exist, no rearrangement is needed; just remove the node.

3. Final Answer:

   The node is simply removed with no further changes needed. -> Option C

4. Quick Check:

   Leaf node deletion = simple removal [OK]

Hint: Leaf nodes delete by direct removal, no child rearrangement needed [OK]

Common Mistakes:

• Thinking children must replace the node
• Assuming tree rebalancing is always needed
• Confusing leaf with internal node deletion

2. Which of the following Rust function signatures correctly represents a BST node deletion method that returns the updated tree root?

easy

A. fn delete_node(root: Option, key: i32) -> Option

B. fn delete_node(root: &Node, key: i32) -> Node

C. fn delete_node(root: Box<Node>, key: i32) -> Box<Node>

D. fn delete_node(root: &mut Node, key: i32) -> &Node

Solution

1. Step 1: Understand Rust ownership for BST nodes

   BST nodes are often wrapped in Option to allow empty children and ownership transfer.

2. Step 2: Correct function signature for deletion

   Deletion may change the root, so returning Option is needed to reflect updated tree.

3. Final Answer:

   fn delete_node(root: Option, key: i32) -> Option -> Option A

4. Quick Check:

   Ownership and optional root = Option [OK]

Hint: Use Option for nullable owned nodes in Rust [OK]

Common Mistakes:

• Using references without ownership transfer
• Returning plain Node instead of Option
• Using &Node which is immutable reference

3. Given the BST with nodes [10, 5, 15, 3, 7, 12, 18], what is the in-order traversal output after deleting node 15?

medium

A. [3, 5, 7, 10, 12, 18]

B. [3, 5, 7, 10, 12]

C. [3, 5, 7, 10, 18]

D. [3, 5, 7, 10, 12, 15, 18]

Solution

1. Step 1: Identify node 15 deletion case

   Node 15 has two children: 12 (left) and 18 (right). We replace 15 with its in-order successor (minimum in right subtree), which is 18.

2. Step 2: Perform deletion and in-order traversal

   Replace 15 with 18, then remove original 18 node (leaf). The tree nodes become [10, 5, 18, 3, 7, 12]. In-order traversal is sorted: [3, 5, 7, 10, 12, 18].

3. Final Answer:

   [3, 5, 7, 10, 12, 18] -> Option A

4. Quick Check:

   In-order after deletion = sorted nodes without 15 [OK]

Hint: Replace deleted node with in-order successor for two children case [OK]

Common Mistakes:

• Removing 18 instead of replacing 15 with 18
• Forgetting to remove original successor node
• Incorrect in-order traversal order

4. Consider this Rust code snippet for BST deletion. What is the bug?

fn delete_node(root: Option<Box<Node>>, key: i32) -> Option<Box<Node>> {
    let mut node = root.unwrap();
    if key < node.val {
        node.left = delete_node(node.left, key);
    } else if key > node.val {
        node.right = delete_node(node.right, key);
    } else {
        if node.left.is_none() {
            return node.right;
        } else if node.right.is_none() {
            return node.left;
        }
        let min_node = find_min(node.right.as_ref().unwrap());
        node.val = min_node.val;
        node.right = delete_node(node.right, min_node.val);
    }
    Some(node)
}

medium

A. find_min should take ownership, not a reference.

B. Using unwrap() causes panic if root is None.

C. Returning node.right or node.left directly causes ownership errors.

D. The function does not handle the case when key equals node.val.

Solution

1. Step 1: Analyze None handling

   The code calls root.unwrap() without checking if root is None, causing a panic on empty tree.

2. Step 2: Correct handling

   Add "if root.is_none() { return None; }" before unwrap.

3. Final Answer:

   Using unwrap() causes panic if root is None. -> Option B

4. Quick Check:

   unwrap without None check = panic [OK]

Hint: Check Option::is_none() before unwrap() [OK]

Common Mistakes:

• Ignoring Rust ownership rules on Option
• Using unwrap() without checking None
• Misunderstanding reference vs ownership in find_min

5. You have a BST with nodes [20, 10, 30, 5, 15, 25, 35]. You delete node 10, which has two children. After deletion, what is the correct new in-order traversal of the BST?

hard

A. [5, 15, 20, 25, 30, 35, 10]

B. [5, 10, 15, 20, 25, 30, 35]

C. [5, 15, 20, 25, 30]

D. [5, 15, 20, 25, 30, 35]

Solution

1. Step 1: Identify deletion of node with two children

   Node 10 has children 5 and 15. We replace 10 with its in-order successor, which is 15.

2. Step 2: Adjust tree and perform in-order traversal

   Replace 10 with 15, then remove original 15 node. The BST nodes become [20, 15, 30, 5, 25, 35]. In-order traversal is sorted: [5, 15, 20, 25, 30, 35].

3. Final Answer:

   [5, 15, 20, 25, 30, 35] -> Option D

4. Quick Check:

   In-order after deletion = sorted nodes without 10 [OK]

Hint: Replace deleted node with in-order successor for two-child nodes [OK]

Common Mistakes:

• Leaving deleted node in traversal
• Not replacing with in-order successor
• Incorrect traversal order