Delete a node from a BST
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): [[]]
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;}