```
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""
prev, curr = None, root
# 1. find the node
while curr and curr.val != key:
prev = curr
curr = curr.left if key < curr.val else curr.right
# 2. check if node exists
if curr is None:
return root
# 3. check if there exists a successor to the node
if curr.right is None:
# 4. check if the node is the root
if curr is root:
return root.left
# node is internal to the tree
if prev.left is curr:
prev.left = curr.left
else:
prev.right = curr.left
curr.left = None
return root
# 5. find inorder successor
prev_succ, succ = curr, curr.right
while succ.left:
prev_succ = succ
succ = succ.left
# 6. swap the values
curr.val = succ.val
# 7. handle the right child of the successor
if prev_succ is curr:
prev_succ.right = succ.right
else:
prev_succ.left = succ.right
succ.right = None
return root
```