BST Delete Operation in DSA Python - Execution Trace

Concept Flow - BST Delete Operation

Start at root

↓

Compare key with current node

↓

Key < node

↓

Go left

↓

Key == node?

↓

No node

↓

Stop

↓

One child

↓

Replace with child

↓

Done

↓

Done

The delete operation in a BST searches for the node, then removes or replaces it depending on its children, ensuring the BST property remains.

Execution Sample

DSA Python

def delete_node(root, key):
    if not root:
        return root
    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        # Node found, handle deletion
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            # Two children: replace with inorder successor
            temp = root.right
            while temp.left:
                temp = temp.left
            root.val = temp.val
            root.right = delete_node(root.right, temp.val)
    return root

This code recursively searches for the node with the given key and deletes it, handling leaf nodes, nodes with one child, and nodes with two children.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Visual State
1	Start at root, compare key=20 with node=30	30	None	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:40│ │ left:──┼──→ │left:∅ │ │left:∅ │ │ right:─┼──→ │right:∅│←── │right:∅│ └────────┘ └────────┘ └────────┘ root
2	Key 20 < 30, go left	20	None	┌────────┐ │ data:20│ │ left:∅ │ │ right:∅│ └────────┘ left child of 30
3	Node 20 found, delete node with no children (leaf)	20	root.left = None	┌────────┐ ┌────────┐ │ data:30│ │ data:40│ │ left:∅ │ │left:∅ │ │ right:─┼──→ │right:∅│ └────────┘ └────────┘ root
4	Deletion complete, return updated root	30	None	┌────────┐ ┌────────┐ │ data:30│ │ data:40│ │ left:∅ │ │left:∅ │ │ right:─┼──→ │right:∅│ └────────┘ └────────┘ root

💡 Node with key 20 deleted; it was a leaf node, so simply removed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
root	Node(30)	Node(30)	Node(30)	Node(30)	Node(30)
current node	Node(30)	Node(20)	Node(20)	None	Node(30)
root.left	Node(20)	Node(20)	Node(20)	None	None
root.right	Node(40)	Node(40)	Node(40)	Node(40)	Node(40)

Key Moments - 3 Insights

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

Because the inorder successor is the smallest node in the right subtree, replacing with it keeps the BST property intact. See step 3 where deletion differs if node has two children.

What happens if the node to delete is a leaf node?

We simply remove it by setting the parent's pointer to None, as shown in step 3 where root.left changes from Node(20) to None.

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

To find the node with the key by moving down the tree, as shown in steps 1 and 2 where we compare and move left or right.

Visual Quiz - 3 Questions

Look at the execution table, what is the pointer change at step 3?

A root.right = None

B root.left = None

C root = None

D No pointer change

💡 Hint

Check the 'Pointer Changes' column at step 3 in the execution_table.

At which step does the node with key 20 get removed from the tree?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Operation' and 'Visual State' columns to see when deletion happens.

If the node to delete had two children, which operation would happen next after finding the node?

A Replace with inorder successor

B Remove node directly

C Go left subtree

D Stop without deletion

💡 Hint

Refer to the concept_flow diagram showing the two children case.

Concept Snapshot

BST Delete Operation:
- Search node by comparing key with current node
- If leaf node: remove directly
- If one child: replace node with child
- If two children: replace with inorder successor
- Recursively update pointers to maintain BST property

Full Transcript

The BST delete operation starts at the root and compares the key to delete with the current node's value. If the key is smaller, it moves left; if larger, it moves right. When the node is found, three cases arise: if it's a leaf node, it is removed by setting the parent's pointer to None; if it has one child, the node is replaced by its child; if it has two children, it is replaced by its inorder successor (the smallest node in the right subtree), and then the successor node is deleted. This process ensures the BST property remains intact after deletion.

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's children are moved up to replace it.

B. The entire tree is rebuilt from scratch.

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

D. The root node is always changed.

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, simply remove the node and update its parent's pointer to null.

3. Final Answer:

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

4. Quick Check:

   Leaf node deletion = simple removal [OK]

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

Common Mistakes:

• Thinking children need rearrangement
• Assuming root always changes
• Believing tree rebuild is needed

2. Which of the following is the correct Python function signature to delete a node with a given key from a BST?

easy

A. def deleteNode(key):

B. def deleteNode(root, key):

C. def deleteNode(root):

D. def deleteNode(key, root):

Solution

1. Step 1: Identify required parameters

   To delete a node, we need the BST root and the key to delete.

2. Step 2: Check function signature

   Only def deleteNode(root, key): has both parameters in correct order.

3. Final Answer:

   def deleteNode(root, key): -> Option B

4. Quick Check:

   Function needs root and key [OK]

Hint: Delete needs root and key parameters [OK]

Common Mistakes:

• Swapping parameter order
• Missing one parameter
• Using only key or root alone

3. Given the BST below, what is the inorder traversal after deleting node 10?

       15
      /  \
    10    20
   /  \     \
  8   12    25

medium

A. [8, 12, 15, 20]

B. [8, 10, 12, 15, 20, 25]

C. [8, 15, 20, 25]

D. [8, 12, 15, 20, 25]

Solution

1. Step 1: Delete node 10 with two children

   Node 10 has two children (8 and 12). Replace it with its inorder successor (12).

2. Step 2: Adjust tree and perform inorder traversal

   After replacement, node 12 replaces 10, and 12's original position is removed. Inorder traversal is [8, 12, 15, 20, 25].

3. Final Answer:

   [8, 12, 15, 20, 25] -> Option D

4. Quick Check:

   Inorder after delete = [8, 12, 15, 20, 25] [OK]

Hint: Replace deleted node with inorder successor [OK]

Common Mistakes:

• Not replacing node with successor
• Leaving deleted node in traversal
• Incorrect traversal order

4. The following code attempts to delete a node from a BST but causes an error. What is the main issue?

def deleteNode(root, key):
    if not root:
        return root
    if key < root.val:
        deleteNode(root.left, key)
    elif key > root.val:
        deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        temp = findMin(root.right)
        root.val = temp.val
        deleteNode(root.right, temp.val)
    return root

medium

A. Recursive calls do not update root's children pointers.

B. The base case is missing.

C. The function does not handle leaf nodes.

D. The function uses an undefined findMin function.

Solution

1. Step 1: Check recursive calls for updating children

   Recursive calls like deleteNode(root.left, key) do not assign the result back to root.left, so changes are lost.

2. Step 2: Correct by assigning returned subtree

   We must write root.left = deleteNode(root.left, key) and root.right = deleteNode(root.right, key) to update pointers properly.

3. Final Answer:

   Recursive calls do not update root's children pointers. -> Option A

4. Quick Check:

   Update children with recursive call results [OK]

Hint: Assign recursive call results to children [OK]

Common Mistakes:

• Ignoring returned subtree after recursion
• Assuming in-place changes without assignment
• Missing base case (not the main issue here)

5. You want to delete a node with two children in a BST. Which approach correctly maintains BST properties after deletion?

hard

A. Replace the node with its inorder predecessor or successor, then delete that node.

B. Replace the node with its left child only.

C. Replace the node with its right child only.

D. Remove the node and leave a gap in the tree.

Solution

1. Step 1: Understand deletion of node with two children

   Direct removal breaks BST rules; we must replace the node with a suitable value.

2. Step 2: Use inorder predecessor or successor

   Replacing with inorder predecessor (max in left subtree) or successor (min in right subtree) keeps BST order intact.

3. Step 3: Delete the replaced node recursively

   After replacement, delete the predecessor/successor node which will have at most one child.

4. Final Answer:

   Replace the node with its inorder predecessor or successor, then delete that node. -> Option A

5. Quick Check:

   Use inorder predecessor/successor for two-child deletion [OK]

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

Common Mistakes:

• Replacing with only left or right child
• Removing node without replacement
• Breaking BST ordering rules