Binary Search Trees Using the ordering
391. Delete Node in a BST
You are given root, the root node of a binary search tree, and an integer key. Delete the node that holds
key, if there is one, and return the root of the tree that is left. That tree must still be a binary
search tree, and it must hold every other value of the original tree.
In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. The values in the tree are distinct.
Often more than one tree is a right answer, so the output does not show the shape. It lists the values
of the tree you return in order: the left subtree first, then the node, then the right subtree, at every node.
A tree lists its values from smallest to largest only when it is a binary search tree. So a right answer
prints the remaining values, sorted, and an empty tree prints [].
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out.
Example 1
Input: root = [50, 30, 70, 20, 40, 60, 80, null, null, 35, 45]
key = 30
[20,35,40,45,50,60,70,80]Explanation: The node 30 has two children. After it is deleted, the tree must still hold 20, 35, 40, 45, 50, 60, 70 and 80, in a valid order. More than one tree shape does that, and any of them is accepted.
Example 2
Input: root = [8, 3, 10], key = 5
[3,8,10]Explanation: No node holds 5, so the tree stays as it is.
Example 3
Input: root = [-1000000000], key = -1000000000
[]Explanation: The only node is deleted, so the tree is empty.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
0 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
- The tree is a binary search tree, and its values are distinct.
-109 ≤ key ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.