BST

Deleting Node

Deleting a node in a Binary Search Tree (BST) requires careful handling of three distinct cases to maintain the BST property. Let’s understand the process visually first.

Visual representation of BST deletion casesLet’s visualize the decision-making process for node deletion:

flowchart LR
    Start["Node to Delete"] --> Check{"Node Found?"}
    Check -->|No| End["Return NULL"]
    
    Check -->|Yes| Children{"Child Count?"}
    
    Children -->|"Zero"| Case1["Case 1:
    Return NULL"]
    
    Children -->|"One"| Case2["Case 2:
    Replace with Child"]
    
    Children -->|"Two"| Case3["Case 3:
    Find Successor"]
    
    Case3 --> Successor["Copy Successor Value"]
    Successor --> Delete["Delete Successor"]

    classDef decision fill:#FFD700,stroke:#DAA520,color:#000
    classDef action fill:#98FB98,stroke:#228B22,color:#000
    classDef endpoint fill:#87CEEB,stroke:#4682B4,color:#000
    
    class Check,Children decision
    class Case1,Case2,Case3,Successor,Delete action
    class Start,End endpoint

Let’s examine each case in detail:

Case 1: Deleting a Leaf Node (No Children)

• Simply remove the node and return NULL
• Example: Deleting node 2 in the first example above
• Maintains BST property automatically as no child relationships need to be preserved

Case 2: Deleting a Node with One Child

• Replace the node with its single child
• Example: Deleting node 3 in the second example above
• Child can be either left or right child
• Preserves BST property by maintaining the correct ordering of values

Case 3: Deleting a Node with Two Children

• Most complex case requiring careful handling

• Process:

  1. Find the successor (smallest value in right subtree)/ Find the predecessor (greatest value in left subtree)
  2. Copy successor’s value to the node being deleted
  3. Delete the successor node (which will be a leaf node or have one child)

• Example: Deleting root node 5 in the third example above

Here’s a complete implementation in Python:

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
 
def get_successor(node):
    """Find the smallest node in the right subtree"""
    curr = node.right
    while curr.left is not None:
        curr = curr.left
    return curr
 
def delete_node(root, key):
    """Delete a node with given key from BST"""
    if root is None:
        return root
    
    # Search for the node to delete
    if key < root.key:
        root.left = delete_node(root.left, key)
    elif key > root.key:
        root.right = delete_node(root.right, key)
    else:
        # Case 1: No children
        if root.left is None and root.right is None:
            root = None
            
        # Case 2: One child (right child)
        elif root.left is None:
            root = root.right
            
        # Case 2: One child (left child)
        elif root.right is None:
            root = root.left
            
        # Case 3: Two children
        else:
            successor = get_successor(root)
            root.key = successor.key
            root.right = delete_node(root.right, successor.key)
            
    return root

Time and Space Complexity

• Time Complexity: O(h) where h is the height of the tree

  • Best case (balanced tree): O(\log n)
  • Worst case (skewed tree): O(n)

• Space Complexity:

  • Recursive implementation: O(h) due to recursion stack
  • Iterative implementation: O(1) extra space

Important Considerations

1. Handle edge cases carefully:

• Empty tree
• Root node deletion
• Node not found in tree

2. BST property must be maintained throughout the deletion process
3. Choose recursive or iterative approach based on memory constraints:

• Recursive: Simpler code but higher memory usage
• Iterative: More complex code but constant extra space

This implementation ensures that the BST maintains its ordering property after deletion while handling all possible scenarios efficiently.