Delete a node from a BST

Medium

Problem

Delete the node with a given key from a BST and return the root, keeping the BST property. There are three cases: the node is a leaf, it has one child, or it has two children (replace it with its in-order successor or predecessor).

Example 1

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

Also asked as: Deletion of a node in a BST

Test cases

Case 1

Input:    [5,3,6,2,4,null,7], 3
Expected (any of): [[5,4,6,2,null,null,7],[5,2,6,null,4,null,7]]

Case 2

Input:    [5,3,6,2,4,null,7], 0
Expected (any of): [[5,3,6,2,4,null,7]]

Case 3

Input:    [], 0
Expected (any of): [[]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Three cases: leaf, one child, two children

Time O(h)Space O(h)

Leaf → remove. One child → splice it in. Two children → replace the value with the in-order successor (leftmost of the right subtree), then delete that successor.

function deleteNode(root, key) {
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 {
if (!root.left) return root.right;
if (!root.right) return root.left;
let succ = root.right;
while (succ.left) succ = succ.left;
root.val = succ.val;
root.right = deleteNode(root.right, succ.val);
}
return root;
}