leetExpert
Practice

Delete Node in a BST

Module 18 · BST & Ordered Structures

Problem

Given the root of a binary search tree and a key, delete the node with value key (if it exists) and return the root of the modified tree. The result must still be a valid BST.

Examples

Example 1

Inputroot = [5,3,6,2,4,null,7], key = 3Output[5,4,6,2,null,null,7]

Explanation. or promote 2 instead of 4

Example 2

Inputroot = [5,3,6,2,4,null,7], key = 5Output[6,3,7,2,4]

Explanation. 5 replaced by inorder successor 6

text
      5                         5
     / \                       / \
    3   6     delete 3         4   6
   / \   \                    /     \
  2   4   7                  2       7

      5                         6
     / \                       / \
    3   6     delete 5         3   7
   / \   \                    / \
  2   4   7                  2   4

Constraints

0 ≤ n ≤ 10⁴ nodes · −10⁵ ≤ values ≤ 10⁵ · values are distinct

Attempt it first

Deletion is the hardest of the three core operations, and the reason is worth discovering yourself. Insert always lands at a clean empty leaf; delete can rip a node out of the middle of the tree, leaving up to two orphaned subtrees that must be reattached without breaking the invariant. Before revealing anything, enumerate the cases by how many children the target node has — there are three — and work out which one is genuinely tricky and why.