BST Delete Operation in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new BST node with the given value.

DSA C

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = [1];
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Drag options to blanks, or click blank then click option'

Anode

Bval

Cvalue

Ddata

Attempts:

3 left

💡 Hint

Common Mistakes

Using an undefined variable like 'data' or 'val' instead of 'value'.

Forgetting to assign the value to the node's data field.

The new node's data field should be set to the given value parameter.

2fill in blank

medium

Complete the code to insert a value into the BST correctly.

DSA C

struct Node* insert(struct Node* root, int value) {
    if (root == NULL) {
        return createNode([1]);
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;
}

Drag options to blanks, or click blank then click option'

Avalue

BNULL

Croot

Droot->data

Attempts:

3 left

💡 Hint

Common Mistakes

Passing root->data instead of value to createNode.

Returning root instead of creating a new node when root is NULL.

When the root is NULL, we create a new node with the value to insert.

3fill in blank

hard

Fix the error in the code to find the minimum value node in a BST.

DSA C

struct Node* findMinNode(struct Node* node) {
    struct Node* current = node;
    while (current->[1] != NULL) {
        current = current->left;
    }
    return current;
}

Drag options to blanks, or click blank then click option'

Aright

Bleft

Cdata

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Checking right child instead of left child.

Checking data or parent pointer which is not correct here.

To find the minimum node, we keep going left until left child is NULL.

4fill in blank

hard

Fill both blanks to correctly delete a node with two children in BST.

DSA C

struct Node* deleteNode(struct Node* root, int value) {
    if (root == NULL) return root;
    if (value < root->data) {
        root->left = deleteNode(root->left, [1]);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, [2]);
    } else {
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }
        struct Node* temp = findMinNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Drag options to blanks, or click blank then click option'

Avalue

Broot->data

Ctemp->data

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using root->data or temp->data instead of value in recursive calls.

Passing root instead of value causing infinite recursion.

We recursively delete the node with the given value in left or right subtree.

5fill in blank

hard

Fill all three blanks to complete the BST delete function handling all cases.

DSA C

struct Node* deleteNode(struct Node* root, int value) {
    if (root == NULL) return root;
    if (value < root->data) {
        root->left = deleteNode(root->left, [1]);
    } else if (value > root->data) {
        root->right = deleteNode(root->right, [2]);
    } else {
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return [3];
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }
        struct Node* temp = findMinNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Drag options to blanks, or click blank then click option'

Avalue

Broot->data

Ctemp

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Returning root instead of the child pointer after deletion.

Using wrong variable in recursive calls.

The recursive calls use the value to delete, and when deleting a node with one child, return the child pointer.

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