Just a standard delete operation in CLRS.
I don't like the way in my code which is used to keep node's parent.
I don't like pass it as an function argument either.
So, guys, which way to keep the node's parent is better? or maybe there's a smarter way.
class Solution(object): def deleteNode(self, root, key): """ :type root: TreeNode :type key: int :rtype: TreeNode """ # iteratively # idea from CLRS current = root self.previous = None self.root = root while current and current.val != key: self.previous = current if current.val < key: current = current.right else: current = current.left if not current: return self.root if not current.right: self.transplant(current.left, current) elif not current.left: self.transplant(current.right, current) else: tmp = self.previous # find_min operation may change the previous, which is current's parent successor = self.find_min(current.right) if successor != current.right: self.transplant(successor.right, successor) successor.right = current.right self.previous = tmp # revocer current's parent self.transplant(successor, current) successor.left = current.left return self.root def transplant(self, from_node, to_node): to_parent = self.previous if not to_parent: self.root = from_node elif to_node == to_parent.left: to_parent.left = from_node else: to_parent.right = from_node def find_min(self, root): assert(root is not None) while root.left: self.previous = root root = root.left return root