### recursive:

I got the almost the same code as https://discuss.leetcode.com/topic/68920/bottom-up-recursive-python-solution-o-log-n-time.

### iterative:

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
```