DSA problem
Delete Node in a BST
Given the root of a binary search tree and a key, delete the node with the given key from the BST and return the (possibly new) root. The shape of the resulting tree must still satisfy the BST invariant. If key is not present in the tree, return the tree unchanged.
Deletion in a BST is a two-step process: first locate the target node (a logarithmic-time descent using the ordering invariant), then perform the local fix to maintain the BST property. There are three structural cases for the node being deleted.
Case 1 — the target is a leaf: simply remove it (return null up the recursion). Case 2 — the target has exactly one child: splice the child up into the target's position (return the non-null child). Case 3 — the target has two children: replace its value with the value of its in-order successor (the leftmost node of the right subtree), then recursively delete that successor from the right subtree. Using the successor preserves the ordering: the successor is the smallest value greater than the target, so swapping it in keeps every left descendant smaller and every right descendant greater.
The optimal recursive implementation runs in O(h) time, where h is the tree height. The recursion stack adds O(h) auxiliary space. Each call performs at most one constant-time pointer rewire, and the recursion follows a single root-to-leaf path.
Examples
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[]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 binary search tree.
- -10^5 <= key <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.