BST Delete Operation in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after deleting a leaf node in BST

Consider the following Rust code that builds a BST and deletes a leaf node. What is the printed BST in-order traversal after deletion?

DSA Rust

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

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

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

fn insert(root: &mut Option<Rc<RefCell<TreeNode>>>, val: i32) {
    match root {
        None => *root = Some(TreeNode::new(val)),
        Some(node) => {
            if val < node.borrow().val {
                insert(&mut node.borrow_mut().left, val);
            } else {
                insert(&mut node.borrow_mut().right, val);
            }
        }
    }
}

fn inorder(root: &Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
    if let Some(node) = root {
        inorder(&node.borrow().left, vals);
        vals.push(node.borrow().val);
        inorder(&node.borrow().right, vals);
    }
}

fn find_min(node: Rc<RefCell<TreeNode>>) -> Rc<RefCell<TreeNode>> {
    let mut current = node;
    while let Some(left) = current.borrow().left.clone() {
        current = left;
    }
    current
}

fn delete_node(root: &mut Option<Rc<RefCell<TreeNode>>>, key: i32) {
    if let Some(node) = root {
        if key < node.borrow().val {
            delete_node(&mut node.borrow_mut().left, key);
        } else if key > node.borrow().val {
            delete_node(&mut node.borrow_mut().right, key);
        } else {
            if node.borrow().left.is_none() {
                *root = node.borrow().right.clone();
            } else if node.borrow().right.is_none() {
                *root = node.borrow().left.clone();
            } else {
                let min_node = find_min(node.borrow().right.clone().unwrap());
                node.borrow_mut().val = min_node.borrow().val;
                delete_node(&mut node.borrow_mut().right, min_node.borrow().val);
            }
        }
    }
}

fn main() {
    let mut root = None;
    insert(&mut root, 5);
    insert(&mut root, 3);
    insert(&mut root, 7);
    insert(&mut root, 2);
    insert(&mut root, 4);
    insert(&mut root, 6);
    insert(&mut root, 8);

    delete_node(&mut root, 2);

    let mut vals = Vec::new();
    inorder(&root, &mut vals);
    println!("{:?}", vals);
}

A [3, 4, 5, 7, 8]

B [2, 3, 4, 5, 6, 7, 8]

C [3, 4, 5, 6, 7, 8]

D [2, 3, 4, 5, 6, 7]

💡 Hint

Deleting a leaf node removes it from the tree. The in-order traversal prints nodes in sorted order.

Node 2 is a leaf and is removed. The in-order traversal then prints all remaining nodes in ascending order.

❓ Predict Output

intermediate

Output after deleting a node with one child in BST

What is the in-order traversal output after deleting node 7 (which has one child) from the BST?

DSA Rust

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

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

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

fn insert(root: &mut Option<Rc<RefCell<TreeNode>>>, val: i32) {
    match root {
        None => *root = Some(TreeNode::new(val)),
        Some(node) => {
            if val < node.borrow().val {
                insert(&mut node.borrow_mut().left, val);
            } else {
                insert(&mut node.borrow_mut().right, val);
            }
        }
    }
}

fn inorder(root: &Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
    if let Some(node) = root {
        inorder(&node.borrow().left, vals);
        vals.push(node.borrow().val);
        inorder(&node.borrow().right, vals);
    }
}

fn find_min(node: Rc<RefCell<TreeNode>>) -> Rc<RefCell<TreeNode>> {
    let mut current = node;
    while let Some(left) = current.borrow().left.clone() {
        current = left;
    }
    current
}

fn delete_node(root: &mut Option<Rc<RefCell<TreeNode>>>, key: i32) {
    if let Some(node) = root {
        if key < node.borrow().val {
            delete_node(&mut node.borrow_mut().left, key);
        } else if key > node.borrow().val {
            delete_node(&mut node.borrow_mut().right, key);
        } else {
            if node.borrow().left.is_none() {
                *root = node.borrow().right.clone();
            } else if node.borrow().right.is_none() {
                *root = node.borrow().left.clone();
            } else {
                let min_node = find_min(node.borrow().right.clone().unwrap());
                node.borrow_mut().val = min_node.borrow().val;
                delete_node(&mut node.borrow_mut().right, min_node.borrow().val);
            }
        }
    }
}

fn main() {
    let mut root = None;
    insert(&mut root, 5);
    insert(&mut root, 3);
    insert(&mut root, 7);
    insert(&mut root, 6);
    insert(&mut root, 8);

    delete_node(&mut root, 7);

    let mut vals = Vec::new();
    inorder(&root, &mut vals);
    println!("{:?}", vals);
}

A [3, 5, 6, 7, 8]

B [3, 5, 6, 8]

C [3, 5, 8]

D [3, 5, 7, 8]

💡 Hint

Deleting a node with one child replaces it with its child.

Node 7 has one child (6). After deletion, 7 is replaced by 6. The in-order traversal reflects this.

❓ Predict Output

advanced

Output after deleting a node with two children in BST

What is the in-order traversal output after deleting node 5 (which has two children) from the BST?

DSA Rust

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

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

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

fn insert(root: &mut Option<Rc<RefCell<TreeNode>>>, val: i32) {
    match root {
        None => *root = Some(TreeNode::new(val)),
        Some(node) => {
            if val < node.borrow().val {
                insert(&mut node.borrow_mut().left, val);
            } else {
                insert(&mut node.borrow_mut().right, val);
            }
        }
    }
}

fn inorder(root: &Option<Rc<RefCell<TreeNode>>>, vals: &mut Vec<i32>) {
    if let Some(node) = root {
        inorder(&node.borrow().left, vals);
        vals.push(node.borrow().val);
        inorder(&node.borrow().right, vals);
    }
}

fn find_min(node: Rc<RefCell<TreeNode>>) -> Rc<RefCell<TreeNode>> {
    let mut current = node;
    while let Some(left) = current.borrow().left.clone() {
        current = left;
    }
    current
}

fn delete_node(root: &mut Option<Rc<RefCell<TreeNode>>>, key: i32) {
    if let Some(node) = root {
        if key < node.borrow().val {
            delete_node(&mut node.borrow_mut().left, key);
        } else if key > node.borrow().val {
            delete_node(&mut node.borrow_mut().right, key);
        } else {
            if node.borrow().left.is_none() {
                *root = node.borrow().right.clone();
            } else if node.borrow().right.is_none() {
                *root = node.borrow().left.clone();
            } else {
                let min_node = find_min(node.borrow().right.clone().unwrap());
                node.borrow_mut().val = min_node.borrow().val;
                delete_node(&mut node.borrow_mut().right, min_node.borrow().val);
            }
        }
    }
}

fn main() {
    let mut root = None;
    insert(&mut root, 5);
    insert(&mut root, 3);
    insert(&mut root, 7);
    insert(&mut root, 2);
    insert(&mut root, 4);
    insert(&mut root, 6);
    insert(&mut root, 8);

    delete_node(&mut root, 5);

    let mut vals = Vec::new();
    inorder(&root, &mut vals);
    println!("{:?}", vals);
}

A [2, 3, 4, 5, 6, 7, 8]

B [3, 4, 6, 7, 8]

C [2, 3, 4, 5, 6, 7]

D [2, 3, 4, 6, 7, 8]

💡 Hint

Deleting a node with two children replaces it with its in-order successor (smallest node in right subtree).

Node 5 is replaced by node 6 (in-order successor). Node 6 is then deleted from its original position.

🔧 Debug

advanced

Identify the error in BST delete function

What error will this Rust code produce when deleting a node from the BST?

DSA Rust

fn delete_node(root: &mut Option<Rc<RefCell<TreeNode>>>, key: i32) {
    if let Some(node) = root {
        if key < node.borrow().val {
            delete_node(&mut node.borrow_mut().left, key);
        } else if key > node.borrow().val {
            delete_node(&mut node.borrow_mut().right, key);
        } else {
            if node.borrow().left.is_none() {
                *root = node.borrow().right.clone();
            } else if node.borrow().right.is_none() {
                *root = node.borrow().left.clone();
            } else {
                let min_node = find_min(node.borrow().right.clone().unwrap());
                node.borrow_mut().val = min_node.borrow().val;
                delete_node(&mut node.borrow_mut().right, min_node.borrow().val);
            }
        }
    }
}

// Assume TreeNode and find_min are defined as before.

A Runtime panic due to multiple mutable borrows of node

B No error, runs correctly

C Logical error: deletes wrong node value

D Compilation error: missing lifetime specifier

💡 Hint

Look at how mutable borrows are used inside the recursive calls.

The code tries to borrow node mutably multiple times simultaneously, causing a runtime panic in Rust due to borrow rules.

🧠 Conceptual

expert

Minimum number of nodes in BST after deleting root with two children

Given a BST with 7 nodes, if the root node has two children and is deleted using the standard BST delete operation, what is the minimum number of nodes remaining in the BST?

A 6

B 5

C 4

D 7

💡 Hint

Deleting a node with two children replaces it with its in-order successor, which is then deleted from its original position.

The in-order successor replaces the deleted node, so the total number of nodes decreases by one.

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