BST Delete: Three Cases
Handle leaf deletion, single-child deletion, and two-child deletion using the in-order successor, implementing the algorithm from scratch.
Why BST Deletion is Tricky
BST deletion is the most complex of the three core operations because removing a node must preserve the BST property for the entire tree. There are three distinct cases depending on the node's children: it has no children (leaf), one child, or two children. Each case requires a different strategy. Interviewers love this problem because it tests pointer manipulation, edge-case thinking, and knowledge of the in-order successor concept.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Three cases for deleting a node:
# Case 1: Leaf node (no children) -> simply remove it
# Case 2: One child -> replace node with its child
# Case 3: Two children -> replace value with in-order successor
# then delete the in-order successor
print('BST delete: 3 cases based on number of children')Case 1: Deleting a Leaf Node
A leaf node has no children. Deletion is simple: return None from the recursive call, which causes the parent to set its pointer (left or right) to null. This is the base case that all BST delete implementations must handle first. Verify this works for the special case where the tree has only one node (the root is a leaf).
def find_min(node):
while node.left:
node = node.left
return node
# Demonstrating leaf deletion:
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(1) # leaf
root.left.right = TreeNode(4) # leaf
# To delete node 1 (leaf): set root.left.left = None
root.left.left = None
print(root.left.left) # None -- deleted
print(root.left.val) # 3 still intact