Delete Node in BST Solution

function deleteNode(root, key):
    if root == null:
        return null
    if key < root.val:
        root.left = deleteNode(root.left, key)
    else if key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        // Found 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 = deleteNode(root.right, successor.val)
    return root

Time: $O(h)$ for search plus $O(h)$ to find and delete successor = $O(h)$ total.

The recursive call to delete the successor is guaranteed to hit case 1 or 2 (successor has no left child by definition).