All problems

Delete Node in a BST

Medium · tree dfs

You are given the root of a binary search tree (BST) and an integer key. Remove the node whose value is key and return the root of the resulting tree. If no node holds key, return the tree unchanged.

Several trees could be left after a removal, so the result is fixed by these rules. Let x be the node to remove:

• If x has no children, it is simply removed.
• If x has one child, that child (together with everything below it) takes the place of x.
• If x has two children, find its in-order successor: the smallest value in the right subtree of x. The successor's value is placed in x's position, and the successor's own node is then removed from the right subtree by the rules above.

All values in the tree are distinct, so at most one node matches. The root may be the node removed, and the result may be the empty tree.

Examples

Example 1

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

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

The node 3 has two children. Its in-order successor is 4, the smallest value in its right subtree, so 4 takes its place.

Example 2

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

Output: [5, 3, 6, 2, 4, null, 7]

No node holds 0, so the tree is returned as it was.

Example 3

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

Output: [6, 3, 7, 2, 4]

The root has two children. The smallest value in its right subtree is 6, which moves up; the old node 6 is replaced by its only child, 7.

Constraints

• The number of nodes is in the range [0, 500].
• -10^4 <= Node.val <= 10^4, and all values are distinct.
• -10^4 <= key <= 10^4
• The tree is a valid binary search tree.