Where it runs
1. The problem
In the lesson about the search tree, insert was easy: you walk down and put the new value into an empty place. Delete is harder. Take a value out of the middle of the tree and it leaves a hole. Two whole subtrees hang under that hole (a subtree is a node together with everything below it). Which node should go into the hole is not obvious. Do it carelessly and one subtree gets lost: no link points to it any more. Or the rule "smaller on the left, larger on the right" breaks, and every later search depends on that rule.
You need to remove any value so that the tree stays a valid binary search tree (BST). Every remaining value must sit where a search will look for it.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that remove nodes from a tree and keep the rest intact. Recurse down, assign the returned subtree back to root.left or root.right, and replace a node with two children by its inorder successor.
The lesson task under the same name.
A node below low is replaced by its trimmed right side, a node above high by its trimmed left side.
The same write back of the returned child, and the children of each deleted node become new roots.