BST Deletion

Deletion has three cases:

Case 1: Leaf node. Remove it.

Case 2: One child. Replace node with its child.

Case 3: Two children. Find inorder successor (smallest in right subtree), copy its value to the node, delete the successor.

function delete(root, key):
    if root == null:
        return null
    if key < root.val:
        root.left = delete(root.left, key)
    else if key > root.val:
        root.right = delete(root.right, key)
    else:
        // Found the node to delete
        if root.left == null:
            return root.right
        if root.right == null:
            return root.left
        // Two children: find successor
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = delete(root.right, successor.val)
    return root

Time: $O(h)$.