Deletion in BST in Data Structures Theory - Mini Project: Build & Apply

Deletion in BST

📖 Scenario: Imagine you have a collection of numbers stored in a special tree called a Binary Search Tree (BST). You want to remove a number from this tree while keeping it organized.

🎯 Goal: You will build the steps to delete a node from a BST. This includes setting up the tree, choosing the number to delete, applying the deletion logic, and completing the process.

📋 What You'll Learn

Create a BST with specific nodes

Set a variable for the value to delete

Implement the deletion logic for the BST

Complete the deletion process with proper tree updates

💡 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 deletion is important for software engineers working with data structures, algorithms, and performance optimization.

1

Create the BST nodes

Create a class called Node with attributes value, left, and right. Then create a BST with root node value 50, left child 30, right child 70, left child of 30 as 20, right child of 30 as 40, left child of 70 as 60, and right child of 70 as 80.

Data Structures Theory

# Define Node class and create BST nodes as described
# Your code here

Hint

Start by defining the Node class with the needed attributes. Then create the root and its children exactly as described.

2

Set the value to delete

Create a variable called key and set it to 30. This is the value you want to delete from the BST.

Data Structures Theory

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

root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

# Set the key value to delete
# Your code here

Hint

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

3

Implement the deletion logic

Define a function called deleteNode that takes root and key as parameters. Inside, use recursion to find the node with value key. Handle three cases: node has no child, one child, or two children. For two children, replace with the smallest value in the right subtree.

Data Structures Theory

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

root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

key = 30

# Define deleteNode function below
# Your code here

Hint

Use recursion to find the node. Handle no child, one child, and two children cases carefully. Use a helper function to find the smallest node in the right subtree.

4

Complete the deletion process

Call the deleteNode function with root and key to delete the node. Store the result back in root to update the tree.

Data Structures Theory

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

def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def deleteNode(root, key):
    if root is None:
        return root
    if key  root.value:
        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.value = temp.value
        root.right = deleteNode(root.right, temp.value)
    return root

root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)
root.right.left = Node(60)
root.right.right = Node(80)

key = 30

# Call deleteNode to remove the key from the BST
# Your code here

Hint

Call the deleteNode function with root and key, and assign the result back to root.

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