':type root: TreeNode
:type key: int
:rtype: TreeNode'

def deleteNode(self, root, key):

    if (not root):
        return root
    if (root.val > key):
        root.left = deleteNode(root.left, key)
    elif (root.val < key):
        root.right = deleteNode(root.right, key)
    elif (not root.left):
        right = root.right
        del root
        return right
    elif (not root.right):
        left = root.left
        del root
        return left
    else:
        successor = root.right
        while successor.left:
            successor = successor.left
        root.val = successor.val
        root.right = deleteNode(root.right, successor.val)
    return root
