Skip to content
Onsite
19 / 29

Delete Node in a BST

MediumP2Coding

Given the root of a binary search tree and a value key, delete the node holding key (if present) and return the root of the resulting BST.

Deletion has several valid results, so this problem fixes one:

  • a leaf is removed;
  • a node with one child is replaced by that child;
  • a node with two children takes the value of its in-order successor (the smallest value in its right subtree), and that successor node is then removed from the right subtree.

If key is not in the tree, return the tree unchanged. Values are unique.

Example 1

Input
root = [5,3,6,2,4,null,7], key = 3
Output
[5,4,6,2,null,null,7]
Why
Node 3 has two children. Its successor is 4, so 3 becomes 4 and the old 4 is removed.

Example 2

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

Example 3

Input
root = [], key = 0
Output
[]

Constraints

  • 0 <= number of nodes <= 10^4
  • -10^5 <= Node.val, key <= 10^5
  • Values are unique.

Hints

Run checks the 3 visible tests, Submit all 9.