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

Need a 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

Need a 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

Need a 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

Need a hint?

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