BST Delete Operation in DSA Python - Build from Scratch

BST Delete Operation

📖 Scenario: You are managing a simple phone book stored as a Binary Search Tree (BST). Each node contains a contact's phone number. You want to be able to remove a contact's phone number from this phone book.

🎯 Goal: Build a program that creates a BST with given phone numbers, sets a target phone number to delete, performs the delete operation on the BST, and then prints the BST in sorted order after deletion.

📋 What You'll Learn

Create a BST by inserting given phone numbers in order

Set a variable for the phone number to delete

Implement the BST delete operation for the given phone number

Print the BST nodes in ascending order after deletion

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to organize data for fast search, insert, and delete operations.

💼 Career

Understanding BST delete operation is important for software engineers working on data storage, search engines, and performance-critical applications.

1

Create BST with given phone numbers

Create a class called Node with attributes val, left, and right. Then create a function called insert that inserts a value into the BST. Finally, create a BST by inserting these phone numbers in this order: 50, 30, 70, 20, 40, 60, 80. Store the root node in a variable called root.

DSA Python

# Define Node class and insert function
# Insert phone numbers 50, 30, 70, 20, 40, 60, 80 into BST
# Store root in variable root
# Your code here

Hint

Start by defining the Node class with val, left, and right. Then write the insert function to add nodes correctly. Use a loop to insert all given numbers into the BST.

2

Set the phone number to delete

Create a variable called key and set it to the phone number 30 which you want to delete from the BST.

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

root = None
for number in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, number)

# Set the phone number to delete
# Your code here

Hint

Simply create a variable named key and assign it the value 30.

3

Implement BST delete operation

Write a function called deleteNode that takes root and key as parameters and deletes the node with value key from the BST. Use the standard BST delete logic: if the node has two children, replace it with its inorder successor. Return the new root after deletion.

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

root = None
for number in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, number)

key = 30

# Write deleteNode function below
# Your code here

Hint

Use recursion to find the node to delete. Handle three cases: no child, one child, and two children. For two children, find the smallest node in the right subtree (inorder successor) and replace the current node's value with it, then delete the successor.

4

Print BST in sorted order after deletion

Write a function called inorder that takes root and returns a list of node values in ascending order. Then call deleteNode(root, key) to delete the node, and print the list returned by inorder after deletion.

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.right = deleteNode(root.right, key)
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp
        temp = minValueNode(root.right)
        root.val = temp.val
        root.right = deleteNode(root.right, temp.val)
    return root

root = None
for number in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, number)

key = 30

# Write inorder function and print the BST after deletion
# Your code here

Hint

Use an inorder traversal to get the sorted list of BST values. Call deleteNode(root, key) to delete the node, then print the inorder list.

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