Delete Node in a BST

Given the root of a binary search tree and a key, delete the node with that key and return the root of the updated tree. Pattern focus: BST Insert and Delete. Deletion may require replacing a node with its inorder successor or predecessor to preserve the BST property.

Input Format

root = binary tree root, key = value to delete

Output Format

updated BST root

Constraints

  • 0 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root and key must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

[5,4,6,2,null,null,7]

Explanation:

Node 3 has two children, so it is replaced by its inorder successor.

Example 2:

Input:

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

Output:

[6,3,7,2,4]

Explanation:

Deleting the root promotes the inorder successor 6.

Loading...
Delete Node in a BST - Binary Search Tree