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.
def delete(root, key):
if root == null:
return null
if key < root.val:
root.left = delete(root.left, key)
elif 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: .