Course contentsShow
← Computer Science
Lesson 513 of 2,87212. Binary Search TreesFree lesson

BST Deletion: Complete Implementation

Combine all deletion cases into a complete function handling leaf, one-child, and two-child scenarios.

BST Deletion: Complete Implementation

What You'll Learn

You'll combine all three deletion cases (leaf, one child, two children) into a single, complete function that handles any BST node deletion.

The Complete Picture

You've learned the individual deletion cases separately—now it's time to put them together into one cohesive function. Think of this like a decision tree: when deleting a node, you first locate it, then determine which case applies, and finally execute the appropriate removal strategy.

The Complete Algorithm

Here's the full deletion process:

  1. Search for the node to delete (just like BST search)
  2. Classify which case it falls into:
    • Case 1: Leaf node (no children) → Simply remove it
    • Case 2: One child → Replace node with its child
    • Case 3: Two children → Replace with inorder successor (or predecessor), then delete that successor
def delete(root, key):
    # Base case: empty tree
    if root is None:
        return root
    
    # Search phase
    if key < root.data:
        root.left = delete(root.left, key)
    elif key > root.data:
        root.right = delete(root.right, key)
    else:
        # Node found! Handle deletion cases
        
        # Case 1 & 2: Zero or one child
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        
        # Case 3: Two children
        # Find inorder successor (smallest in right subtree)
        successor = find_minimum(root.right)
        root.data = successor.data
        root.right = delete(root.right, successor.data)
    
    return root

Notice how elegant this is: the function recursively searches, then rebuilds the tree on the way back up. The hardest case (two children) cleverly reduces itself to an easier case by deleting the successor.

Key Takeaway:
A complete BST deletion function combines search with three cases—leaf, one child, and two children—handling each appropriately while maintaining the BST invariant throughout the tree.