Deletion in BST in Data Structures Theory - Step-by-Step Execution

Concept Flow - Deletion in BST

Start at root

↓

Find node to delete

↓

Node found?

No→Stop: Node not in tree

Yes↓

Check children count

↓

No children

→Remove node

↓

One child

→Replace node with child

↓

Two children

→Find inorder successor

↓

Copy successor value

↓

Delete successor node

↓

Done

Start from the root and find the node to delete. If found, handle three cases: no children (remove), one child (replace), two children (replace with inorder successor and delete successor).

Execution Sample

Data Structures Theory

DeleteNode(root, key):
  if root is None:
    return None
  if key < root.val:
    root.left = DeleteNode(root.left, key)
  elif key > root.val:
    root.right = DeleteNode(root.right, key)
  else:
    # Node found, handle deletion cases
    ...

This recursive function finds the node with the given key and deletes it following BST deletion rules.

Analysis Table

Step	Operation	Current Node	Action Taken	Tree State (Inorder)
1	Start at root	50	Compare key=30 with 50, go left	[30, 40, 50, 60, 70]
2	Move to left child	30	Compare key=30 with 30, node found	[30, 40, 50, 60, 70]
3	Check children	30	Node has one child (40)	[30, 40, 50, 60, 70]
4	Delete node	30	Replace node 30 with child 40	[40, 50, 60, 70]
5	Return updated tree	50	Deletion complete	[40, 50, 60, 70]
6	Stop	N/A	Node deleted, stop recursion	[40, 50, 60, 70]

💡 Node with key 30 deleted by replacing it with its single child 40.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
root	50	50	30	30	40	40
key	30	30	30	30	30	30
current_node	50	30	30	30	40	40

Key Insights - 3 Insights

Why do we replace the node with its inorder successor when it has two children?

Replacing with the inorder successor maintains the BST property because the successor is the smallest node in the right subtree, ensuring all left nodes remain smaller and right nodes larger. See execution_table step 3 for the case when two children exist.

What happens if the node to delete has no children?

If the node has no children, it can be removed directly without replacement. This is simpler than other cases. This is implied in the concept_flow under 'No children' case.

Why do we recursively call DeleteNode on left or right subtree?

Because BST is a tree, we must search down the correct subtree to find the node. Recursion helps traverse until the node is found or the subtree is empty. See execution_table steps 1 and 2.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what happens to the node with value 30?

A It is replaced by its child node 40

B It is replaced by its inorder successor

C It is removed without replacement

D It remains unchanged

💡 Hint

Check the 'Action Taken' column at step 4 in execution_table.

At which step does the algorithm confirm the node to delete has been found?

A Step 1

B Step 2

C Step 3

D Step 5

💡 Hint

Look for 'node found' in the 'Action Taken' column in execution_table.

If the node to delete had two children, which additional step would appear in the execution_table?

A Find inorder predecessor

B Replace node with left child

C Find inorder successor and delete it

D Remove node directly

💡 Hint

Refer to concept_flow where two children case leads to finding inorder successor.

Concept Snapshot

Deletion in BST:
- Find node to delete by comparing keys
- If no children: remove node
- If one child: replace node with child
- If two children: replace node with inorder successor (smallest in right subtree) and delete successor
- Recursion helps traverse tree
- Maintains BST property after deletion

Full Transcript

Deletion in a Binary Search Tree (BST) starts by searching for the node with the given key from the root. If the node is not found, the process stops. If found, there are three cases: if the node has no children, it is simply removed; if it has one child, it is replaced by that child; if it has two children, it is replaced by its inorder successor, which is the smallest node in its right subtree, and then the successor node is deleted. This process maintains the BST property. The deletion is typically implemented recursively, traversing left or right subtree depending on the key comparison. The example traced shows deleting node 30 which has one child 40, so 30 is replaced by 40. Variables like root and current_node update as the recursion proceeds. Key confusions include why inorder successor is used for two children case, what happens with no children, and why recursion is needed. The visual quiz tests understanding of these steps and outcomes.

Practice

1. Which of the following is NOT a case handled during deletion in a Binary Search Tree (BST)?

easy

A. Deleting a node with two children

B. Deleting a node with one child

C. Deleting a node with three children

D. Deleting a node with no children (leaf node)

Solution

1. Step 1: Understand BST node children possibilities

   In a BST, each node can have zero, one, or two children. There is no case of three children because BST nodes have at most two children.

2. Step 2: Identify valid deletion cases

   Deletion handles nodes with zero, one, or two children. Three children is impossible, so it is not a valid case.

3. Final Answer:

   Deleting a node with three children -> Option C

4. Quick Check:

   BST nodes have max two children = Deleting node with three children [OK]

Hint: Remember BST nodes have max two children only [OK]

Common Mistakes:

• Thinking a node can have more than two children
• Confusing deletion cases with other tree types
• Ignoring the leaf node deletion case

2. Which of the following is the correct step to delete a node with two children in a BST?

easy

A. Replace the node with its parent node

B. Replace the node with its inorder predecessor (largest in left subtree)

C. Replace the node with any leaf node

D. Replace the node with its inorder successor (smallest in right subtree)

Solution

1. Step 1: Identify deletion method for two children

   When deleting a node with two children, the standard method is to replace it with its inorder successor, which is the smallest node in its right subtree.

2. Step 2: Confirm replacement correctness

   The inorder successor maintains BST properties after replacement, unlike arbitrary leaf or parent nodes.

3. Final Answer:

   Replace the node with its inorder successor (smallest in right subtree) -> Option D

4. Quick Check:

   Two children deletion uses inorder successor = Replace the node with its inorder successor (smallest in right subtree) [OK]

Hint: Use inorder successor for two-child node deletion [OK]

Common Mistakes:

• Using inorder predecessor instead of successor
• Replacing with any leaf node
• Replacing with parent node

3. Consider the BST below:

      15
     /  \
    10  20
   /    / \
  8    17 25

If we delete node 20, what will be the new right child of 15?

medium

A. 17

B. 25

C. 20

D. 15

Solution

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

   Node 20 has two children: 17 (left) and 25 (right).

2. Step 2: Find inorder successor of node 20

   The inorder successor is the smallest node in the right subtree of 20, which is 25. But since 25 has no left child, 25 is the successor.

3. Step 3: Replace node 20 with its inorder successor

   Replace 20 with 25. Then remove original 25 node (which is a leaf). The new right child of 15 becomes 25.

4. Final Answer:

   25 -> Option B

5. Quick Check:

   Inorder successor of 20 is 25 = 25 [OK]

Hint: Replace two-child node with inorder successor (smallest right) [OK]

Common Mistakes:

• Choosing 17 as successor instead of 25
• Not updating parent's child pointer
• Confusing inorder predecessor with successor

4. What is the error in the following deletion logic for a BST node with one child?

if node.left is not None:
    return node.left
else:
    return node.right

medium

A. It incorrectly returns the child without updating parent links

B. It should delete both children instead

C. It only works for leaf nodes

D. It should replace node with inorder successor

Solution

1. Step 1: Analyze deletion logic for one child

   The code returns the child node directly but does not update the parent's pointer to this child, which breaks the BST links.

2. Step 2: Identify missing link update

   Proper deletion requires updating the parent's child pointer to the returned node to maintain tree structure.

3. Final Answer:

   It incorrectly returns the child without updating parent links -> Option A

4. Quick Check:

   Missing parent link update = It incorrectly returns the child without updating parent links [OK]

Hint: Always update parent links when deleting nodes [OK]

Common Mistakes:

• Ignoring parent pointer updates
• Deleting both children unnecessarily
• Using inorder successor for one-child deletion

5. You have a BST where you want to delete the root node which has two children. The inorder successor is the immediate right child with no left child. After replacing the root with the inorder successor, what must you do next to maintain BST properties?

hard

A. Replace the inorder successor with its right child

B. Replace the inorder successor with its left child

C. Do nothing, the tree is already valid

D. Remove the inorder successor node from its original position

Solution

1. Step 1: Replace root with inorder successor

   The root is replaced by its inorder successor, which is the immediate right child with no left child.

2. Step 2: Adjust inorder successor's original position

   Since the inorder successor has no left child, replace it with its right child (which may be None) to maintain BST links.

3. Final Answer:

   Replace the inorder successor with its right child -> Option A

4. Quick Check:

   Inorder successor replaced by right child = Replace the inorder successor with its right child [OK]

Hint: Replace successor with its right child after root replacement [OK]

Common Mistakes:

• Forgetting to remove successor from original spot
• Replacing successor with left child (which doesn't exist)
• Assuming no further action needed