#450 - Delete Node in a BST

MediumBinary Search Tree

Given the root of a BST and a key, delete the node with that key and return the root of the modified BST. The tree must remain a valid BST after deletion.

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

Solution Space

Try it

/**
 * Deletes a node with the given key from a BST.
 *
 * Three cases for the target node:
 * 1. Leaf → simply remove.
 * 2. One child → replace with that child.
 * 3. Two children → replace value with inorder successor
 *    (smallest in right subtree), then delete that successor.
 *
 * @param root Root of the BST
 * @param key  Value to delete
 * @returns    Root of the modified BST
 */
export function deleteNode(
  root: TreeNode | null,
  key: number,
): TreeNode | null {
  if (!root) return null;

  if (key < root.val) {
    root.left = deleteNode(root.left, key);
  } else if (key > root.val) {
    root.right = deleteNode(root.right, key);
  } else {
    // Found the node to delete
    if (!root.left) return root.right;
    if (!root.right) return root.left;

    // Two children: find inorder successor (min of right subtree)
    let successor = root.right;
    while (successor.left) successor = successor.left;

    root.val = successor.val;
    root.right = deleteNode(root.right, successor.val);
  }

  return root;
}

Approach: recursive BST deletion – navigate to the key, then handle three cases (leaf, one child, two children). For two children, replace with the inorder successor and recursively delete it.

Time: O(h) – one path down to find the node, plus one path down to find/delete the successor.

Space: O(h) – recursion stack.

Alternative approaches:

Approach	Idea	Time	Space
Inorder predecessor	Same logic but replace with the largest value in the left subtree	O(h)	O(h)

Why the successor method is preferred: purely conventional — both are equally valid and symmetric.

#1161 Maximum Level Sum of a Binary Tree

#700 Search in a Binary Search Tree