BST Delete Operation in DSA C - Execution Trace

Concept Flow - BST Delete Operation

Start at root

↓

Compare key with current node

↓

Key < node

↓

Go left

↓

Found node to delete?

↓

No

↓

Stop

↓

Replace node with successor or child

↓

Done

The delete operation in a BST starts at the root, traverses left or right based on comparisons, finds the node to delete, then handles three cases: leaf node, node with one child, or node with two children by replacing it appropriately.

Execution Sample

DSA C

deleteNode(root, 20);
// Deletes node with value 20 from BST

Deletes the node with value 20 from the BST, adjusting pointers to maintain BST properties.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Visual State
1	Start at root	50	None	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ data:70│ │ data:20│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ root
2	Compare 20 with 50, go left	50	None	Same as step 1
3	Visit left child	30	None	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ data:70│ │ data:20│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ root current
4	Compare 20 with 30, go left	30	None	Same as step 3
5	Visit left child	20	None	┌────────┐ ┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ data:20│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ root parent current
6	Node to delete found (20), leaf node	20	None	Same as step 5
7	Remove leaf node 20, set parent's left to null	20	parent.left = null	┌────────┐ ┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ data:70│ │ next:──┼──→ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ └────────┘ root left child right child
8	Deletion complete	None	None	Final BST: ┌────────┐ ┌────────┐ ┌────────┐ │ data:50│ │ data:30│ │ data:70│ │ next:──┼──→ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ └────────┘ root left child right child

💡 Node 20 found and deleted; it was a leaf node, so parent's left pointer set to null.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
root	Node 50	Node 50	Node 50	Node 50	Node 50
current	Node 50	Node 30	Node 20	null	null
parent	null	Node 50	Node 30	Node 30	Node 30
parent.left	Node 30	Node 30	Node 20	null	null

Key Moments - 3 Insights

Why do we set parent's left pointer to null after deleting a leaf node?

Because the deleted node has no children, we remove it by making the parent's pointer to it null, as shown in step 7 of the execution_table.

What happens if the node to delete has two children?

We find the inorder successor (smallest node in right subtree), replace the node's data with successor's data, then delete the successor node. This is not shown here but is the next step after finding the node.

Why do we keep track of the parent node during traversal?

We need the parent to update its pointer when deleting the current node, as seen in steps 5 and 7 where parent.left is updated.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which node is current pointing to?

A Node with data 20

B Node with data 30

C Node with data 50

D Null

💡 Hint

Check the 'Node Visited' column at step 5 in execution_table.

At which step does the parent's left pointer get set to null?

A Step 4

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Pointer Changes' column to find when parent.left changes.

If the node to delete had one child, how would the visual state differ at step 7?

A Parent's pointer would point to the child node instead of null

B Parent's pointer would be set to null anyway

C The child node would be deleted too

D No change in pointers

💡 Hint

Recall that for one child, we replace the node with its child, not null.

Concept Snapshot

BST Delete Operation:
- Start at root, traverse left/right by comparing key
- Find node to delete
- If leaf: remove node, set parent's pointer to null
- If one child: replace node with child
- If two children: replace with inorder successor
- Update pointers carefully to maintain BST structure

Full Transcript

The BST delete operation begins at the root node. We compare the key to delete with the current node's data. If the key is smaller, we go left; if larger, we go right. We continue until we find the node to delete. If the node is a leaf (no children), we remove it by setting the parent's pointer to null. If the node has one child, we replace the node with its child. If it has two children, we find the inorder successor (smallest node in the right subtree), replace the node's data with the successor's data, then delete the successor node. Throughout, we keep track of the parent node to update pointers correctly. The execution table shows a step-by-step deletion of a leaf node with value 20, including pointer updates and the final BST structure.

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