BST Delete Operation in DSA Python

Mental Model

Deleting a node in a BST means removing it while keeping the tree sorted and connected.

Analogy: Imagine removing a book from a sorted bookshelf and rearranging nearby books so the order stays perfect.

      5
     / \
    3   7
   / \   \
  2   4   8

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, delete node with value 3

Goal: Remove node 3 and keep BST properties intact

Step 1: Find node 3 to delete

      5
     / \
    [3] 7
   / \   \
  2   4   8

Why: We must locate the node to remove it

Step 2: Node 3 has two children, find its inorder successor (smallest in right subtree)

      5
     / \
    3   7
   / \   \
  2  [4]  8

Why: Inorder successor replaces node 3 to keep BST order

Step 3: Replace node 3's value with 4

      5
     / \
    4   7
   / \   \
  2   4   8

Why: We copy successor's value to node 3

Step 4: Delete original successor node 4 (which has no children)

      5
     / \
    4   7
   /     \
  2       8

Why: Remove duplicate node after replacement

Result:

      5
     / \
    4   7
   /     \
  2       8

Annotated Code

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def find_min(node):
    while node.left:
        node = node.left
    return node

def delete_node(root, key):
    if root is None:
        return root
    if key < root.val:
        root.left = delete_node(root.left, key)  # go left to find key
    elif key > root.val:
        root.right = delete_node(root.right, key)  # go right to find key
    else:
        # found node to delete
        if root.left is None:
            return root.right  # replace node with right child
        elif root.right is None:
            return root.left  # replace node with left child
        # node with two children
        temp = find_min(root.right)  # find inorder successor
        root.val = temp.val  # copy successor's value
        root.right = delete_node(root.right, temp.val)  # delete successor
    return root

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

# Driver code
root = None
for v in [5,3,7,2,4,8]:
    root = insert(root, v)
root = delete_node(root, 3)
print(" -> ".join(map(str, inorder(root))) + " -> null")

if key < root.val: root.left = delete_node(root.left, key) # go left to find key

Traverse left subtree to find node to delete

elif key > root.val: root.right = delete_node(root.right, key) # go right to find key

Traverse right subtree to find node to delete

if root.left is None: return root.right # replace node with right child

If no left child, replace node with right child

elif root.right is None: return root.left # replace node with left child

If no right child, replace node with left child

temp = find_min(root.right) # find inorder successor root.val = temp.val # copy successor's value root.right = delete_node(root.right, temp.val) # delete successor

For two children, replace with inorder successor and delete successor

Output

2 -> 4 -> 5 -> 7 -> 8 -> null

Complexity Analysis

Time: O(h) where h is tree height because we traverse from root to node and possibly to successor

Space: O(h) due to recursion stack in worst case of skewed tree

vs Alternative: Compared to array deletion which can be O(n) due to shifting, BST delete is efficient if tree is balanced

Edge Cases

Deleting a node not present in the tree

Function returns original tree unchanged

DSA Python

if root is None:
    return root

Deleting a leaf node (no children)

Node is simply removed by returning None to parent

DSA Python

if root.left is None:
    return root.right

Deleting root node with one child

Root replaced by its single child

DSA Python

elif root.right is None:
    return root.left

When to Use This Pattern

When you need to remove a value from a BST and keep it sorted, use the BST delete operation pattern to handle all cases cleanly.

Common Mistakes

Mistake: Not handling the two-children case by replacing with inorder successor
Fix: Always find the inorder successor and replace the node's value before deleting the successor

Mistake: Forgetting to update parent's child pointer after deletion
Fix: Return the updated subtree root after deletion and assign it back to parent's left or right

Summary

Deletes a node from a BST while maintaining its sorted structure.

Use when you need to remove elements from a BST without breaking its order.

The key is to replace a node with two children by its inorder successor to keep the BST valid.

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