def deleteNode(root, key):
if not root:
return null
if key < root.val:
root.left = deleteNode(root.left, key)
elif key > root.val:
root.right = deleteNode(root.right, key)
else:
# Found node to delete
if not root.left:
return root.right
if not root.right:
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).