BST Delete Operation in DSA Rust - Time & Space Complexity

Time Complexity: BST Delete Operation

O(h)

Understanding Time Complexity

We want to understand how long it takes to remove a value from a Binary Search Tree (BST).

How does the time needed change when the tree grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn delete_node(root: Option>, key: i32) -> Option> {
    match root {
        None => None,
        Some(mut node) => {
            if key < node.val {
                node.left = delete_node(node.left, key);
                Some(node)
            } else if key > node.val {
                node.right = delete_node(node.right, key);
                Some(node)
            } else {
                // Node to delete found
                if node.left.is_none() {
                    return node.right;
                } else if node.right.is_none() {
                    return node.left;
                }
                // Find min in right subtree
                let mut min_node = node.right.as_ref();
                while let Some(left) = min_node.unwrap().left.as_ref() {
                    min_node = Some(left);
                }
                node.val = min_node.unwrap().val;
                node.right = delete_node(node.right, node.val);
                Some(node)
            }
        }
    }
}
    

This code removes a node with a given value from a BST, adjusting the tree to keep its order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to find the node and adjust the tree.
• How many times: At most once per tree level, going down from root to leaf.
• Additional operation: A small loop to find the minimum node in the right subtree when deleting a node with two children.

How Execution Grows With Input

As the tree grows taller, the number of steps to find and delete a node grows roughly with the height.

Input Size (n)	Approx. Operations
10	About 3 to 4 steps (tree height)
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly as the tree grows, depending on its height, not total nodes.

Final Time Complexity

Time Complexity: O(h)

This means the time to delete depends on the tree height, which is the longest path from root to leaf.

Common Mistake

[X] Wrong: "Deleting a node always takes time proportional to the total number of nodes in the tree."

[OK] Correct: Actually, deletion only needs to follow one path down the tree, so it depends on the height, not all nodes.

Interview Connect

Understanding how deletion time depends on tree height helps you explain efficiency clearly and shows you know how tree shape affects performance.

Self-Check

"What if the BST is always balanced? How would that change the time complexity of deletion?"

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