This problem is actually pretty tough. If you don’t know about how predecessors and successors work in a binary search tree, this problem is going to be pretty hard to solve. You can find the predecessor for a particular node by going left once and then going right until you can’t go right anymore - vice versa for the successor.
Knowing this, we search the binary tree until we find our target node for deletion. If the node is a leaf, we can just set it to None. If the right child exists for a node, we find the successor and replace our current value with the successor’s value. Then we recursively travel the right subtree to delete the successor.
If the right node doesn’t exist, but the left does, we find the predecessor and do the same - setting our value to the predecessor and recursively deleting the predecessor from the left subtree.
The solution is as follows:
class Solution:
def successor(self, root: TreeNode) -> int:
root = root.right
while root.left:
root = root.left
return root.val
def predecessor(self, root: TreeNode) -> int:
root = root.left
while root.right:
root = root.right
return root.val
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return
if key > root.val:
root.right = self.deleteNode(root.right, key)
elif key < root.val:
root.left = self.deleteNode(root.left, key)
else:
if not root.left and not root.right:
root = None
elif root.right:
root.val = self.successor(root)
root.right = self.deleteNode(root.right, root.val)
else:
root.val = self.predecessor(root)
root.left = self.deleteNode(root.left, root.val)
return root_ Time Complexity:
O(h) - Where h is the height of the tree.
_ Space Complexity:
O(h) - Our recursive function can be called h times.