BST Delete Operation in DSA C - Time & Space Complexity

Time Complexity: BST Delete Operation

O(h)

Understanding Time Complexity

We want to understand how the time to delete a node in a Binary Search Tree changes as the tree grows.

Specifically, how does the number of steps depend on the number of nodes in the tree?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Delete a node from BST
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;
    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        // Node found: handle 3 cases
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        // Node with two children: find inorder successor
        Node* temp = minValueNode(root->right);
        root->val = temp->val;
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}
    

This code deletes a node with a given key from a BST by searching for it and then removing it while maintaining BST properties.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive traversal down the tree to find the node to delete.
• How many times: At most once per level of the tree, from root to leaf.
• Additional operation: Finding the inorder successor involves traversing down the right subtree's leftmost path.

How Execution Grows With Input

As the tree grows, the number of steps depends on the height of the tree.

Input Size (n)	Approx. Operations (steps down tree)
10	Up to 4 steps (if tree is balanced)
100	Up to 7 steps
1000	Up to 10 steps

Pattern observation: The steps grow slowly as the tree grows, roughly proportional to the tree height.

Final Time Complexity

Time Complexity: O(h) where h is the height of the BST.

This means the time to delete depends on how tall the tree is, not just how many nodes it has.

Common Mistake

[X] Wrong: "Deleting a node always takes the same time regardless of tree shape."

[OK] Correct: If the tree is unbalanced and looks like a list, the height is large, so deletion takes longer. Balanced trees keep height small, making deletion faster.

Interview Connect

Understanding how tree height affects deletion helps you explain efficiency clearly and shows you know how data structure shape impacts performance.

Self-Check

"What if the BST is always balanced, like an AVL tree? How would the time complexity change?"

Practice

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

easy

A. The node is replaced by its right child.

B. The entire tree is restructured to maintain balance.

C. The node is replaced by its left child.

D. The node is simply removed and its parent's pointer is set to null.

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: Update parent's pointer

   After removal, the parent's pointer to this node is set to null to disconnect it.

3. Final Answer:

   The node is simply removed and its parent's pointer is set to null. -> Option D

4. Quick Check:

   Leaf node deletion = remove node and set parent's pointer null [OK]

Hint: Leaf node deletion just removes node, no child replacement needed [OK]

Common Mistakes:

• Replacing leaf node with child when none exists
• Restructuring entire tree unnecessarily
• Confusing leaf node with internal node deletion

2. Which of the following is the correct syntax to delete a node with value key from a BST in C?

easy

A. root = deleteNode(root, key);

B. deleteNode(root, key);

C. delete(root, key);

D. root.deleteNode(key);

Solution

1. Step 1: Understand function call and assignment

   Deleting a node may change the root, so the returned root must be assigned back.

2. Step 2: Check syntax correctness

   root = deleteNode(root, key); correctly assigns the returned root from deleteNode to root.

3. Final Answer:

   root = deleteNode(root, key); -> Option A

4. Quick Check:

   Assign returned root after deletion [OK]

Hint: Always assign returned root after deletion to handle root changes [OK]

Common Mistakes:

• Not assigning returned root causing lost tree updates
• Using incorrect function names
• Using object-oriented syntax in C

3. Given the BST below and the code snippet to delete node with value 15:

      20
     /  \
   10    30
     \     \
     15    40

root = deleteNode(root, 15);

What will be the in-order traversal of the BST after deletion?

medium

A. [20, 30, 40]

B. [10, 15, 20, 30, 40]

C. [10, 20, 30, 40]

D. [10, 20, 15, 30, 40]

Solution

1. Step 1: Delete node 15 from BST

   Node 15 is a leaf node, so it is removed directly.

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

   In-order traversal visits nodes in ascending order: 10, 20, 30, 40.

3. Final Answer:

   [10, 20, 30, 40] -> Option C

4. Quick Check:

   In-order after deleting 15 = [10, 20, 30, 40] [OK]

Hint: In-order traversal after leaf deletion excludes that node [OK]

Common Mistakes:

• Including deleted node in traversal
• Confusing traversal order
• Assuming node replaced incorrectly

4. Consider this buggy C code snippet for deleting a node from BST:

struct Node* deleteNode(struct Node* root, int key) {
  if (root == NULL) return root;
  if (key < root->data)
    deleteNode(root->left, key);
  else if (key > root->data)
    deleteNode(root->right, key);
  else {
    // deletion logic here
  }
  return root;
}

What is the main bug in this code?

medium

A. The deletion logic is missing for leaf nodes.

B. The recursive calls do not update root->left or root->right pointers.

C. The function does not handle the case when root is NULL.

D. The function returns root instead of void.

Solution

1. Step 1: Analyze recursive calls

   Recursive calls are made but their results are not assigned back to root->left or root->right.

2. Step 2: Understand pointer update necessity

   Without updating pointers, the tree structure won't change after deletion.

3. Final Answer:

   The recursive calls do not update root->left or root->right pointers. -> Option B

4. Quick Check:

   Update child pointers with recursive call results [OK]

Hint: Always assign recursive call results back to child pointers [OK]

Common Mistakes:

• Ignoring pointer updates after recursion
• Missing base case for NULL root
• Confusing return types

5. You have a BST with nodes: 50, 30, 70, 20, 40, 60, 80. You delete node 50 (the root). Which node replaces the root to maintain BST properties?

hard

A. The minimum node from the right subtree (60)

B. The maximum node from the left subtree (40)

C. The node 70 directly replaces 50

D. The node 30 directly replaces 50

Solution

1. Step 1: Identify node to replace root on deletion

   When deleting a node with two children, replace it with the inorder successor (minimum in right subtree).

2. Step 2: Find minimum node in right subtree of 50

   Right subtree nodes: 70, 60, 80. Minimum is 60.

3. Final Answer:

   The minimum node from the right subtree (60) -> Option A

4. Quick Check:

   Root replacement = inorder successor (min right subtree) [OK]

Hint: Replace deleted node with inorder successor (min right subtree) [OK]

Common Mistakes:

• Replacing with max left subtree instead of min right
• Replacing with direct child without checking BST rules
• Confusing inorder predecessor and successor