- When found the node, put right child of the node to the right of the right most leaf node of left child. That way the values are still in order.
- Return the left child of the node(skip root, a.k.a delete it). If the node doesn't have left child, return right child.
- Otherwise do binary search. If key < root.val, change left child to the returned new root. Do right child if key > root.val.
This solution always runs in O(log(n)) time since when it finds the node to delete, it goes to the right most leaf of the left sub-tree to put right sub-tree of the node there.
class Solution(object): def deleteNode(self, root, key): """ :type root: TreeNode :type key: int :rtype: TreeNode """ if not root: return None if root.val == key: if root.left: # Find the right most leaf of the left sub-tree left_right_most = root.left while left_right_most.right: left_right_most = left_right_most.right # Attach right child to the right of that leaf left_right_most.right = root.right # Return left child instead of root, a.k.a delete root return root.left else: return root.right # If left or right child got deleted, the returned root is the child of the deleted node. elif root.val > key: root.left = self.deleteNode(root.left, key) else: root.right = self.deleteNode(root.right, key) return root
@boy27910231 The answer is accepted by OJ and of course is very brilliant one, but I think it has a potential to increase the height of the tree with the delete method called on.
@Ipeq1 Yes you are right. This solution is kind of a shortcut, which messes up the tree height. But since the description doesn't require the tree remain balanced after deletion, I just went with the easy way. To maintain balanced, we still have to use the traditional way.