450. Delete Node in a BST

Practice Delete Node in a BST for free on NudgeCode: Medium, Binary Tree pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Given the root of a binary search tree and a value key, delete the node whose value is key (if there is one) and return the root of the updated tree.

The result must be a valid BST that holds every value of the original tree except key. Many trees satisfy this: for example, a deleted node with two children can be replaced by its in-order successor or by its in-order predecessor. Any valid BST with exactly those values passes; the expected value is one of them. If key is not in the tree, return the tree unchanged.

Example

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

[5,2,6,null,4,null,7] is also accepted.

Constraints

• 0 <= number of nodes <= 10^4
• -10^5 <= Node.val, key <= 10^5
• All values in the tree are unique