I got the almost the same code as https://discuss.leetcode.com/topic/68920/bottom-up-recursive-python-solution-o-log-n-time.
Keep track of the parent node and the found node. After we find the node whose value is the key, we manipulate the sub tree starting from the found node.
class Solution(object): def deleteNode(self, root, key): """ :type root: TreeNode :type key: int :rtype: TreeNode """ if root is None: return None parent = None nodeFound = root while nodeFound and nodeFound.val != key: parent = nodeFound if nodeFound.val < key: nodeFound = nodeFound.right else: nodeFound = nodeFound.left if nodeFound is None: # no node! return root subRoot = None if nodeFound.left is None: subRoot = nodeFound.right else: currNode = nodeFound.left while currNode.right is not None: currNode = currNode.right currNode.right = nodeFound.right subRoot = nodeFound.left if parent is None: return subRoot if parent.left == nodeFound: parent.left = subRoot if parent.right == nodeFound: parent.right = subRoot return root