Delete Node in a BST

Difficulty: Medium Source: NeetCode

Problem

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. The deletion can be divided into two stages: search for a node to remove, and if the node is found, delete the node.

Example 1: Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7]

Example 2: Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7]

Constraints:

The number of nodes in the tree is in the range [0, 10^4]

-10^5 <= Node.val <= 10^5

Each node has a unique value

root is a valid BST

-10^5 <= key <= 10^5

Prerequisites

Before attempting this problem, you should be comfortable with:

BST Property — Used to locate the node to delete
Inorder Successor — The smallest value in the right subtree; used to replace a deleted node with two children
Recursive Tree Modification — Returning updated subtree roots to rewire the tree

1. Recursive DFS

Intuition

Deletion has three distinct cases depending on how many children the target node has:

No children (leaf): Just remove it — return null to the parent
One child: Replace the node with its only child
Two children: Can’t just remove it. Replace its value with the inorder successor (smallest in the right subtree), then delete the successor from the right subtree

Algorithm

If root is null, return null (key not found)
If key < root.val, recurse left: root.left = delete(root.left, key)
If key > root.val, recurse right: root.right = delete(root.right, key)
Otherwise, root is the node to delete:
- No left child → return root.right
- No right child → return root.left
- Two children → find min in right subtree, set root.val = min.val, delete min from right subtree
Return root

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def delete_node(root, key):
    if not root:
        return None  # Key not found

    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        # Found the node to delete
        if not root.left:
            return root.right  # No left child: replace with right
        if not root.right:
            return root.left   # No right child: replace with left

        # Two children: find inorder successor (min in right subtree)
        successor = root.right
        while successor.left:
            successor = successor.left

        # Replace value with successor's value
        root.val = successor.val
        # Delete the successor from the right subtree
        root.right = delete_node(root.right, successor.val)

    return root

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# --- tests ---
root1 = build_tree([5, 3, 6, 2, 4, None, 7])
print("Before:", inorder(root1))  # [2, 3, 4, 5, 6, 7]
root1 = delete_node(root1, 3)
print("After deleting 3:", inorder(root1))  # [2, 4, 5, 6, 7]

root2 = build_tree([5, 3, 6, 2, 4, None, 7])
root2 = delete_node(root2, 0)  # Key not in tree
print("After deleting 0:", inorder(root2))  # [2, 3, 4, 5, 6, 7]

root3 = build_tree([5, 3, 6, 2, 4, None, 7])
root3 = delete_node(root3, 5)  # Delete root
print("After deleting root 5:", inorder(root3))  # [2, 3, 4, 6, 7]

# Delete a leaf
root4 = build_tree([5, 3, 6, 2, 4, None, 7])
root4 = delete_node(root4, 2)
print("After deleting leaf 2:", inorder(root4))  # [3, 4, 5, 6, 7]

Complexity

Time: O(h) — search takes O(h), finding successor takes O(h), deletion takes O(h)
Space: O(h) — recursion stack

Forgetting to reassign root.left and root.right. The recursive call returns the updated subtree root. If you don’t assign root.left = delete(root.left, key), the tree won’t actually be modified.

Handling the two-children case incorrectly. A common mistake is trying to physically remove the successor node before updating the current node’s value, causing issues. The correct order is: copy the successor’s value into the current node, then delete the successor from the right subtree.

Confusing inorder successor with inorder predecessor. You can use either (min of right subtree OR max of left subtree) — both are valid. Just be consistent.

Note Book