450. Delete Node in a BST
Model: qwen3.5:9b
Topics: Tree
FAANG asked: 1
Acceptance rate: 45.5%
Problem Breakdown
We are given a Binary Search Tree (BST) root node reference and an integer key. Our goal is to remove the node containing this key while maintaining the BST property: for any node, all values in its left subtree must be smaller, and all values in its right subtree must be larger.
Inputs:
root: The top-level pointer of a valid BST (can be empty).key: An integer value to delete from the tree.
Outputs:
- A reference to the root node of the modified BST after deletion. If no change occurred, return original root; if deleted successfully, return new structure’s root.
Implicit Constraints & Edge Cases:
- BST Property Preservation: The inorder traversal sequence must remain sorted even after modification. We cannot simply delete a node and leave its children dangling or swap values arbitrarily without checking order constraints.
- Node with Two Children: This is the trickiest case. If we remove an internal node, one of its descendants (either in-order predecessor or successor) must take its place to preserve ordering. The standard approach uses the In-Order Successor (smallest value in right subtree).
- Empty Tree / Key Not Found: We need to handle cases where
rootis null initially or we traverse down without finding the key, returning the original root unchanged.
Intuition
First, I recognize this as a standard BST search problem combined with pointer manipulation. The first step is always searching for the node matching the key. If it doesn’t exist (we hit a leaf and didn’t find it), we return immediately.
Once found at some subtree level, deletion logic depends on how many children that specific node has:
- Leaf Node: Simply remove the pointer to this child from its parent. In recursion terms, if
rootis the target, just return null (or handle via caller). - One Child: Replace the current node with its single existing child. This maintains order because that child already satisfies BST constraints relative to the grandparent.
- Two Children: We cannot simply pick a random replacement; we must maintain sorted order. The standard strategy is to find the In-Order Successor (the smallest value in the right subtree). Why? Because it’s guaranteed to be larger than everything on the left and smaller than everything else in the right, effectively “sliding” into the current node’s spot before being removed from its original position recursively.
This suggests a recursive approach where each function call returns the new root of that specific subtree after deletion is handled locally or propagated up.
Approach
I will use recursion because it naturally handles tree traversal and pointer updates by returning modified subtrees to parents. The algorithm follows these steps:
- Base Case: If
rootis null, return None (key not found in this branch). - Search Logic: Compare current node value with key.
- If
key < root.val: Recurse left (deleteNode(root.left)), then assign result toroot.left. Returnroot. - If
key > root.val: Recurse right, updateroot.right, returnroot.
- If
- Found Case (
root.val == key): This is the deletion point. We need a new node reference here.- No Children: Return None (effectively deleting this subtree).
- One Child: Check if left or right exists. If one does, return that child directly to replace current
root. - Two Children: Find the In-Order Successor of the current node. The successor is found by going down the rightmost path from the left subtree? No, standard convention for BST deletion often uses the smallest value in the right subtree (In-order Successor). To do this efficiently: find min(node.right), then replace
root.valwith that successor’s val and delete the duplicate node recursively. Alternatively, splice the entire tree by attaching root.left to root.right.min(). I will implement finding the In-Order Successor from the right child for clarity in recursion logic (replace value of current node with successor, then recurse on right).
Complexity Analysis
- Time: where H is the height of the tree. We traverse down once to find the key () and potentially another path to find the inorder successor if two children exist ( in worst case skewed trees), but since we do this within one traversal depth, it remains linear with respect to height.
- Space: due to recursion stack usage for traversing down the tree. In a balanced BST H is , making space logarithmic; in a skewed tree (linked list) H is .
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def deleteNode(root, key):
# Base case: if tree is empty or node not found in this branch
if root is None:
return None
# If target key is smaller than current value, go left and update pointer with new subtree result
if key < root.val:
root.left = deleteNode(root.left, key)
# If target key is larger, go right and update pointer
elif key > root.val:
root.right = deleteNode(root.right, key)
# Key found at current node (root.val == key), handle deletion here
else:
# Case 1 or 2: Node has no children or one child.
# Return the non-null child to replace this node in parent's pointer.
if root.left is None and root.right is None:
return None
elif root.left is not None and root.right is None:
return root.left
elif root.left is None and root.right is not None:
return root.right
# Case 3: Node has two children.
# Find In-Order Successor (smallest value in right subtree) to replace current node's value.
else:
successor = findMin(root.right)
# Replace current node's value with the successor's value
root.val = successor.val
# Delete the duplicate successor from its original position recursively
root.right = deleteNode(root.right, successor.val)
return root
def findMin(node):
"""Helper to traverse right until leaf."""
while node.left:
node = node.left
return node
Edge Cases Handled
- Empty Tree (
rootis None): The function returnsNone, preserving the empty state. - Key Not Found: Recursion bottoms out at nulls without finding key, returning original structure unchanged up to root level.
- Deleting a Leaf Node: Logic falls through base cases; parent’s pointer set to
None. - Deleting a Node with One Child: Returns the single child node directly as replacement for current subtree.
- Deleting a Node with Two Children: Finds successor, updates value, and recursively deletes the duplicate from right subtree (effectively removing the original leaf that was moved).