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

↓

0 or 1 child

↓

Replace node

↓

Delete node

↓

Delete successor

↓

Done

The delete operation in a BST searches for the node, then deletes it based on its children count: no child, one child, or two children with inorder successor replacement.

Execution Sample

DSA C#

Delete(20) on BST:
      30
     /  \
   20    40
  /  \
10   25

Deletes node with value 20 which has two children, replacing it with its inorder successor.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Visual State
1	Start at root	30	None	30 / \ 20 40 / \ 10 25
2	Compare key 20 with 30	30	Move left pointer to 20	30 / \ 20 40 / \ 10 25
3	Compare key 20 with 20	20	Found node to delete	30 / \ 20 40 / \ 10 25
4	Node 20 has two children	20	Find inorder successor (leftmost in right subtree)	30 / \ 20 40 / \ 10 25
5	Inorder successor is 25	25	None	30 / \ 20 40 / \ 10 25
6	Replace 20's value with 25	20	Node 20 data changed to 25	30 / \ 25 40 / \ 10 25
7	Delete successor node 25 (leaf)	25	Remove 25 from right subtree of 25	30 / \ 25 40 / 10
8	Deletion complete	N/A	None	30 / \ 25 40 / 10

💡 Node with key 20 deleted by replacing with inorder successor 25 and removing successor node.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 6	After Step 7	Final
currentNode	30	20	20	20 (value changed to 25)	25 (successor node)	null (deleted)
parentNode	null	30	30	30	20 (node with replaced value)	20
inorderSuccessor	null	null	null	25	25	null
BST Visual	Initial tree	Moved left to 20	Found node 20	20 replaced by 25	Successor 25 deleted	Final tree

Key Moments - 3 Insights

Why do we replace the node's value with the inorder successor's value instead of just deleting the node?

Because the node has two children, directly deleting it would break the BST structure. Replacing its value with the inorder successor (smallest node in right subtree) keeps the BST property intact. See execution_table steps 4-6.

What happens to the inorder successor node after its value is copied?

The inorder successor node is deleted because its value was copied up. Since it is either a leaf or has one child, it can be safely removed. See execution_table step 7.

Why do we move left when key < current node during search?

Because in BST, left child nodes have smaller values. So if key is less, we go left to find the node. See execution_table step 2.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of the node originally holding 20?

A 25

B 20

C 30

D 10

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 6 where node 20's value is replaced.

At which step is the inorder successor node actually removed from the tree?

A Step 4

B Step 5

C Step 7

D Step 8

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns to find when the successor node is deleted.

If the node to delete had only one child, how would the pointer changes differ?

A Replace node with inorder successor

B Replace node with its child directly

C Do nothing

D Delete entire subtree

💡 Hint

Refer to the concept_flow where 0 or 1 child case replaces node with child directly.

Concept Snapshot

BST Delete Operation:
- Search node by comparing key
- If node has 0 or 1 child: replace node with child or null
- If node has 2 children: find inorder successor (leftmost in right subtree)
- Replace node's value with successor's value
- Delete successor node (leaf or single child)
- Maintains BST property after deletion

Full Transcript

The BST delete operation starts at the root and searches for the node with the given key by comparing values and moving left or right accordingly. When the node is found, if it has no or one child, it is replaced directly by its child or null. If it has two children, the inorder successor is found by going to the right subtree and then as far left as possible. The node's value is replaced with the inorder successor's value, and then the successor node is deleted, which is simpler because it has at most one child. This process keeps the BST structure valid. The execution steps show visiting nodes 30, 20, then replacing 20 with 25, and finally deleting the successor node 25. Variables track current node, parent, and successor during the process. Key confusions include why replacement is needed for two children and what happens to the successor node after copying. The visual quiz tests understanding of these steps and pointer changes.

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 from the root.

C. The node is replaced by its left child.

D. The node is simply removed without affecting other nodes.

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: Effect on BST structure

   Since no children exist, no restructuring is needed; just remove the node.

3. Final Answer:

   The node is simply removed without affecting other nodes. -> Option D

4. Quick Check:

   Leaf node deletion = simple removal [OK]

Hint: Leaf nodes delete by direct removal only [OK]

Common Mistakes:

• Thinking the tree restructures after leaf deletion
• Replacing leaf node with a child that doesn't exist
• Confusing leaf node deletion with internal node deletion

2. Which of the following is the correct C# syntax to delete a node with value 10 from a BST using a method named DeleteNode?

easy

A. root.DeleteNode(10);

B. root = DeleteNode(root, 10);

C. DeleteNode(root, 10);

D. DeleteNode(10, root);

Solution

1. Step 1: Understand method signature

   Usually, BST delete methods return the new root after deletion, so assignment is needed.

2. Step 2: Correct method call syntax

   Calling DeleteNode(root, 10) returns updated root, so root = DeleteNode(root, 10); is correct.

3. Final Answer:

   root = DeleteNode(root, 10); -> Option B

4. Quick Check:

   Assign returned root after deletion [OK]

Hint: Assign returned root after delete call [OK]

Common Mistakes:

• Not assigning the returned root after deletion
• Calling delete as instance method on root node
• Passing arguments in wrong order

3. Given the BST below and the C# code to delete node 15, what is the in-order traversal output after deletion?

      20
     /  \
   10    30
     
     15

root = DeleteNode(root, 15);

medium

A. [10, 20, 30]

B. [10, 15, 20, 30]

C. [20, 30]

D. [10, 20, 15, 30]

Solution

1. Step 1: Identify node to delete and its position

   Node 15 is a leaf node (no children) under 10.

2. Step 2: Delete node 15 and perform in-order traversal

   After deleting 15, in-order traversal visits nodes in ascending order: 10, 20, 30.

3. Final Answer:

   [10, 20, 30] -> Option A

4. Quick Check:

   In-order after deleting leaf = sorted without deleted node [OK]

Hint: In-order skips deleted leaf node [OK]

Common Mistakes:

• Including deleted node in traversal output
• Misordering nodes in traversal
• Confusing pre-order or post-order with in-order

4. Consider this C# method snippet for deleting a node from a 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 {
    if (root.left == null) return root.right;
    else if (root.right == null) return root.left;
    root.val = MinValue(root.right);
    root.right = DeleteNode(root.right, root.val);
  }
  return root;
}

What is the bug in this code?

medium

A. The method does not update root.left or root.right after recursive calls.

B. The method does not handle the case when both children exist properly.

C. The method does not handle deleting leaf nodes correctly.

D. The method does not return the updated root after deletion.

Solution

1. Step 1: Analyze deletion when both children exist

   The method correctly replaces root's value with the minimum in the right subtree and deletes that minimum node recursively.

2. Step 2: Check correctness of recursive updates

   The method updates root.left and root.right after recursive calls, so this is handled properly.

3. Step 3: Identify the actual bug

   There is no bug in handling both children case or returning root; the code is correct.

4. Final Answer:

   None of the provided options correctly identify a bug. -> Option A

Hint: Check both children case carefully [OK]

Common Mistakes:

• Thinking leaf deletion is buggy here
• Missing recursive update of child pointers
• Assuming method forgets to return root

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. Node 30 (left child of root)

B. Node 40 (maximum in left subtree)

C. Node 60 (minimum in right subtree)

D. Node 70 (right child of root)

Solution

1. Step 1: Identify node to delete and its children

   Node 50 is root with two children: left subtree (30, 20, 40) and right subtree (70, 60, 80).

2. Step 2: Find replacement node for root deletion

   Standard BST deletion replaces node with minimum node in right subtree, which is 60.

3. Final Answer:

   Node 60 (minimum in right subtree) -> Option C

4. Quick Check:

   Root replaced by min right subtree node [OK]

Hint: Replace deleted node with min right subtree node [OK]

Common Mistakes:

• Replacing with max left subtree instead of min right
• Replacing with immediate child without checking subtree
• Confusing replacement rules for BST deletion