Implement Insertion, Search, and Deletion Operations for a Binary Search Tree (BST)

Implement Insertion, Search, and Deletion Operations for a Binary Search Tree (BST)

Problem Description
A Binary Search Tree (BST) is a special type of binary tree that satisfies the following properties:

  • For each node in the tree, all values in its left subtree are less than the node's value.
  • All values in its right subtree are greater than the node's value.
  • The left and right subtrees are also binary search trees.

This problem requires you to implement three fundamental operations for a BST: inserting a new node, searching for a node with a specific value, and deleting a node with a specific value.

Basic Structure
First, we need to define the node structure for the BST:

class TreeNode:
    def __init__(self, val=0):
        self.val = val      # Node value
        self.left = None    # Left child node
        self.right = None   # Right child node

Insert Operation
The goal of the insert operation is to add a new node to the BST while preserving the BST properties.

Step-by-step Breakdown:

  1. Base Case: If the tree is empty (root is None), directly create a new node as the root.
  2. Compare Values:
    • If the value to insert is less than the current node's value, recursively insert into the left subtree.
    • If the value to insert is greater than the current node's value, recursively insert into the right subtree.
    • If the values are equal, handle it according to specific requirements (typically, BSTs do not allow duplicate values).

Detailed Process:

def insert(root, val):
    # Base case: reached an empty position, create a new node
    if root is None:
        return TreeNode(val)
    
    # Recursive insertion
    if val < root.val:
        root.left = insert(root.left, val)  # Insert into left subtree
    elif val > root.val:
        root.right = insert(root.right, val)  # Insert into right subtree
    
    return root  # Return the updated root node

Search Operation
The search operation looks for a node with a specific value in the BST.

Step-by-step Breakdown:

  1. Base Case 1: If the tree is empty or the target value is found, return the current node.
  2. Compare Values:
    • If the target value is less than the current node's value, continue searching in the left subtree.
    • If the target value is greater than the current node's value, continue searching in the right subtree.

Detailed Process:

def search(root, val):
    # Base case: tree is empty or target found
    if root is None or root.val == val:
        return root
    
    # Determine search direction based on value comparison
    if val < root.val:
        return search(root.left, val)  # Search in left subtree
    else:
        return search(root.right, val)  # Search in right subtree

Delete Operation
The delete operation is the most complex of the three, requiring handling of three different cases.

Three Deletion Cases:

  1. Node to delete is a leaf node: Delete it directly.
  2. Node to delete has only one child: Replace the deleted node with its child.
  3. Node to delete has two children: Find the minimum node in the right subtree (or the maximum node in the left subtree) to replace it.

Step-by-step Breakdown:

def delete(root, val):
    if root is None:
        return root  # Tree is empty, return directly
    
    # 1. Find the node to delete
    if val < root.val:
        root.left = delete(root.left, val)  # Delete from left subtree
    elif val > root.val:
        root.right = delete(root.right, val)  # Delete from right subtree
    else:
        # 2. Found the node to delete, handle the three cases
        
        # Case 1: Node has only one child or no children
        if root.left is None:
            return root.right  # Replace with right child
        elif root.right is None:
            return root.left   # Replace with left child
        
        # Case 2: Node has two children
        # Find the minimum node in the right subtree (in-order successor)
        temp = find_min(root.right)
        
        # Replace current node's value with the successor's value
        root.val = temp.val
        
        # Delete the successor node from the right subtree (it has at most one right child now)
        root.right = delete(root.right, temp.val)
    
    return root

def find_min(node):
    """Find the minimum node in the subtree rooted at node"""
    current = node
    while current.left is not None:
        current = current.left
    return current

Operation Example
Taking the insertion sequence [5, 3, 7, 2, 4, 6, 8] as an example:

  1. Insertion Process:

    • Insert 5: Becomes the root node.
    • Insert 3: 3 < 5, becomes the left child of 5.
    • Insert 7: 7 > 5, becomes the right child of 5.
    • Insert 2: 2 < 5 → 2 < 3, becomes the left child of 3.
    • And so on...

  2. Deleting Node 3 (which has two children):

    • Find the minimum node in 3's right subtree (4).
    • Replace 3 with 4.
    • Delete the original 4 (this node has no left child).

Time Complexity Analysis

  • Average Case: O(log n), when the tree is relatively balanced.
  • Worst Case: O(n), when the tree degenerates into a linked list (e.g., inserting a sorted sequence).
  • Insertion, search, and deletion all have the same time complexity, which depends on the height of the tree.

Key Points

  1. The properties of a BST ensure efficient searching.
  2. The delete operation is challenging, especially when handling nodes with two children.
  3. Maintaining BST balance is crucial; otherwise, performance degrades.
  4. In practical applications, balanced BSTs (such as AVL trees or Red-Black trees) are often used.