BST Delete Operation in DSA C

Mental Model

Deleting a node from a BST means removing it while keeping the tree sorted. We find the node, then fix the tree by rearranging nodes if needed.

Analogy: Imagine a bookshelf sorted by book titles. Removing a book means taking it out and shifting or replacing books so the order stays correct.

      5
     / \
    3   7
   / \   \
  2   4   8

Dry Run Walkthrough

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

Goal: Remove node 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

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: To replace node 3, we find the next bigger value to keep BST order

Step 3: Replace node 3's value with 4, then delete node 4 which has no children

      5
     / \
    4   7
   /     \
  2       8

Why: Replacing keeps BST order; deleting leaf node 4 is simple

Result:

      5
     / \
    4   7
   /     \
  2       8

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for BST
typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

// Create new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Insert value into BST
Node* insert(Node* root, int val) {
    if (root == NULL) return newNode(val);
    if (val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

// Find minimum value node in BST
Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != NULL) {
        current = current->left; // advance to leftmost node
    }
    return current;
}

// Delete node with given value from BST
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root; // base case: empty tree

    if (key < root->val) {
        root->left = deleteNode(root->left, key); // go left
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key); // go right
    } else {
        // found node to delete
        if (root->left == NULL) {
            Node* temp = root->right; // no left child
            free(root);
            return temp; // replace with right child
        } else if (root->right == NULL) {
            Node* temp = root->left; // no right child
            free(root);
            return temp; // replace with left child
        }

        // node with two children: get inorder successor
        Node* temp = minValueNode(root->right);
        root->val = temp->val; // copy successor value
        root->right = deleteNode(root->right, temp->val); // delete successor
    }
    return root;
}

// Print BST inorder
void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->val);
        inorder(root->right);
    }
}

int main() {
    Node* root = NULL;
    int values[] = {5, 3, 7, 2, 4, 8};
    int n = sizeof(values)/sizeof(values[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);
    }

    printf("Original BST inorder: ");
    inorder(root);
    printf("\n");

    root = deleteNode(root, 3);

    printf("BST inorder after deleting 3: ");
    inorder(root);
    printf("\n");

    return 0;
}

if (root == NULL) return root; // base case: empty tree

stop if tree is empty or node not found

if (key < root->val) { root->left = deleteNode(root->left, key); // go left } else if (key > root->val) { root->right = deleteNode(root->right, key); // go right }

search for node to delete by comparing values

if (root->left == NULL) { Node* temp = root->right; // no left child free(root); return temp; // replace with right child } else if (root->right == NULL) { Node* temp = root->left; // no right child free(root); return temp; // replace with left child }

handle nodes with zero or one child by replacing with child

Node* temp = minValueNode(root->right); root->val = temp->val; // copy successor value root->right = deleteNode(root->right, temp->val); // delete successor

for two children, replace with inorder successor and delete successor

Output

Original BST inorder: 2 3 4 5 7 8 

BST inorder after deleting 3: 2 4 5 7 8 

Complexity Analysis

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

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

vs Alternative: Compared to array deletion which can be O(n) due to shifting, BST delete is faster if tree is balanced

Edge Cases

Deleting from empty tree

Function returns immediately without error

DSA C

if (root == NULL) return root; // base case: empty tree

Deleting leaf node (no children)

Node is removed and parent's pointer set to NULL

DSA C

if (root->left == NULL) { ... } else if (root->right == NULL) { ... }

Deleting node with one child

Node replaced by its single child

DSA C

if (root->left == NULL) { ... } else if (root->right == NULL) { ... }

Deleting node with two children

Node replaced by inorder successor and successor deleted

DSA C

Node* temp = minValueNode(root->right);

When to Use This Pattern

When you need to remove a value from a BST and keep it sorted, use the BST delete operation pattern that handles three cases: leaf, one child, two children.

Common Mistakes

Mistake: Not handling the two children case correctly by just deleting the node without replacement
Fix: Replace node with inorder successor or predecessor before deleting to keep BST properties

Mistake: Forgetting to update parent's pointer after deletion
Fix: Return the new subtree root after deletion and assign it back to parent's child pointer

Summary

Deletes a node from a BST while maintaining the tree's sorted order.

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

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 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