450. Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.

2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

Deletion is more complicated than the two operations we mentioned before. There are also many different strategies for deletion. We are going to introduce one of them which minimizes the changes. Our solution is to replace the target node with a proper child. According to the number of its children, we should consider three different cases:1. If the target node has no child, we can simply remove the node. 2. If the target node has one child, we can use its child to replace itself. 3. If the target node has two children, replace the node with its in-order successor or predecessor node and delete that node.

Here are examples of different cases to help you understand this strategy.

By understanding the strategy above, you should be able to implement deletion function on your own. We have done an exercise about finding the inorder successor in a BST in the previous section. The solution for that question might help you implement the deletion function.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):    
	def deleteNode(self, root, key):
		if not root:  # for the first root, if it is None, return None.
			return None

		# Modify either root, root.left or root.right and return the modified root
		if key < root.val:
			root.left = self.deleteNode(root.left, key) # neet to reassign the returned root to the proper child
		elif key > root.val:
			root.right = self.deleteNode(root.right, key) # neet to reassign the returned root to the proper child
		else: # found the target root
			if not root.left and not root.right: # target root has no children
				return None
			elif not root.left:  # target root has RIGHT child, replace root with the RIGHT child
				return root.right
			elif not root.right:  # target root has LEFT child, replace root with the LEFT child
				return root.left
			else:   # When root has both left and right children
				# Find the successor, replace root.val with successor.val, deleteNode(successor).
				# In this way, we don't need to know the parent of target root to delete the target root.
				successor = self.findSuccessorInRightChild(root) # Since currently root mush have left and right child, we only need to find the successor in the RIGHT child branch. This would be easier compared to maintain a stack of successors, which is sepcifically designed to find both the right child successor and successor in the other part of the tree.
				root.val = successor.val # replace root value with successor value will help us not thinking to much about the parent root of the target root / successor(since successor also need to be deleted and it will be the target root for the next recursive loop).
				
				'''
				This is WROING!!!! 
				We should modify root / root.left / root.right and return root, not return deleteNode(succesor, successor.val)
				Only return None when the root should be None (if not root.left and not root.right: return None)
				'''
				# return self.deleteNode(, successor.val) # recursively delete 
				'''
				Wrong anwser ends
				'''
				root.right = self.deleteNode(root.right, successor.val)

		return root


	def findSuccessorInRightChild(self, root):        
		cur = root.right        
		while(cur.left):            
			cur = cur.left        
		return cur