Given the root of a BST and a key to delete, return the root of the tree with the key deleted.
Example
I: root = [5,3,6,2,4,null,7], key = 3
5
/ \
3 6
/ \ \
2 4 7
O: [5,4,6,2,null,null,7] or [5,2,6,null,4,null,7]
promote from left subtree
5
/ \
2 6
\ \
4 7
promote from right subtree
5
/ \
4 6
/ \
2 7
Note: The replacing node has to be the largest from the left subtree or the smallest from the right subtree. The immediate child won't work. Check out deleting 5 for example.
Analysis
Deletion is an O(h) operation in BST. That means cannot divide and conquer 2 subtrees. We can only recurse down one path. So simply inserting the entire subtree won't work. We have to promote the next up median value to replace the current root.
D&C Code
If you can do the insertion with D&C, then deletion can be done in the same way.
def findLargest(self, root: TreeNode) -> TreeNode:
if root is None:
return None
if root.right is not None:
return self.findLargest(root.right)
else:
return root
def findSmallest(self, root: TreeNode) -> TreeNode:
if root is None:
return None
if root.left is not None:
return self.findSmallest(root.left)
else:
return root
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
# base
if root is None:
return None
# divide
if key == root.val:
# perform deletion
# 3 cases
if root.left is None and root.right is None:
return None
if root.left is None and root.right is not None:
return root.right
if root.left is not None and root.right is None:
return root.left
# promote largest in the left subtree
# or the smallest in the right subtree
# largest_left_tree = self.findLargest(root.left)
# root.val = largest_left_tree.val
# root.left = self.deleteNode(root.left, largest_left_tree.val)
smallest_right_tree = self.findSmallest(root.right)
root.val = smallest_right_tree.val
root.right = self.deleteNode(root.right, smallest_right_tree.val)
# return the promoted subtree
return root
elif key < root.val:
root.left = self.deleteNode(root.left, key)
return root
else: # k > root.val
root.right = self.deleteNode(root.right, key)
return root
Complexity
Time - 2 parts searching the delete key and searching for the replacement value. The worst case is something like this
20
/ \
5 25
/ \
(22) 30
\
35
/ \
34 40
Say we want to delete 20 and using the smallest on the right subtree replacement strategy. If 22 exists, then we just delete it and it is a leaf node. The worst case is that the next node is the smallest node. Then we have to cascade the delete to 25, to 30, 35, and eventually a leaf node. The base case for the deletion is O(1). Finding the replacement value and cascading the delete will be the height of the tree. Therefore, O(h).
Space - Find the smallest or largest value in BST can be done without recursion. The pure deletion is just O(h).
