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: for search plus to find and delete successor = total.
The recursive call to delete the successor is guaranteed to hit case 1 or 2 (successor has no left child by definition).