BST Delete Operation in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What are the three main cases to consider when deleting a node in a Binary Search Tree (BST)?

1. Node to delete is a leaf (no children).
2. Node to delete has one child.
3. Node to delete has two children.

intermediate

In BST deletion, how do you handle deleting a node with two children?

Replace the node's value with its inorder successor (smallest value in right subtree) or inorder predecessor (largest value in left subtree), then delete that successor/predecessor node.

beginner

What is the inorder successor in a BST?

The node with the smallest value in the right subtree of a given node.

intermediate

Why do we replace a node with its inorder successor or predecessor when deleting a node with two children in a BST?

Because it maintains the BST property by ensuring all left subtree nodes are smaller and right subtree nodes are larger than the replaced node.

beginner

What happens if you delete a leaf node in a BST?

You simply remove the node by setting its parent's pointer to NULL, as it has no children.

Which case requires finding the inorder successor or predecessor during BST deletion?

A Node with one child

B Node with two children

C Node with no children

D Root node only

Only when the node has two children do we replace it with its inorder successor or predecessor.

What is the inorder successor of a node in a BST?

A Any leaf node

B Largest node in left subtree

C Parent node

D Smallest node in right subtree

The inorder successor is the smallest node in the right subtree.

When deleting a leaf node in a BST, what is the main action?

A Replace with inorder successor

B Replace with inorder predecessor

C Remove the node by setting parent's pointer to NULL

D Swap with root node

Leaf nodes are removed by setting the parent's pointer to NULL.

If a node has only one child, how is deletion handled in a BST?

A Replace node with its child

B Replace node with inorder successor

C Replace node with inorder predecessor

D Remove node and set parent's pointer to NULL

The node is replaced by its single child to maintain the BST structure.

Why do we not simply remove a node with two children without replacement?

A It would break the BST property

B It is faster to replace

C It is easier to code

D It does not matter

Removing a node with two children without replacement breaks the BST property.

Explain the steps to delete a node with two children in a BST.

Think about how to keep the tree sorted after deletion.

Describe how deleting a node with one child differs from deleting a leaf node in a BST.

Consider what happens to the child nodes.

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