```
class Solution(object):
def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""
# 1. find the node to be deleted
dummy = TreeNode(0)
dummy.left = root
p = root
parent = dummy
while p is not None and p.val != key:
parent = p
if p.val > key:
p = p.left
else:
p = p.right
if p is None: # not found
return root
# 2. find the minimum of p's right subtree
q_parent = p
q = p.right
if q is None: # p has no right subtree, just promote its left subtree
if parent.left == p:
parent.left = p.left
else:
parent.right = p.left
else:
while q.left is not None:
q_parent = q
q = q.left
# exchange value between the minimum q and p
p.val = q.val
# promote q's right child
if q_parent.left == q:
q_parent.left = q.right
else:
q_parent.right = q.right
return dummy.left
```