Delete a Node from a BST
You are given the root of a binary tree. Delete the node with value key (if there is none, change nothing) and return the root. Use exactly this rule:
- A node with no children is simply removed.
- A node with one child is replaced by that child (and its subtree).
- A node with two children takes the value of the smallest value in its right subtree, and that smallest node is then deleted from the right subtree.
Trees appear in the tests in level order, with null for a missing child, like [3,9,20,null,null,15,7]. Each node is a TreeNode with .val, .left and .right; the class is already defined for you.
Example 1
root [5,3,6,2,4,null,7]
key 3
returns [5,4,6,2,null,null,7]
3 has two children; the smallest in its right subtree is 4, so 3 becomes 4 and the old 4 is removed: [5,4,6,2,None,None,7].
Constraints
0 <= number of nodes <= 100-1000 <= node.val <= 1000- The tree is a valid binary search tree.
-1000 <= key <= 1000
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.