Remove a node and keep the order
Delete a value from a search tree so that it stays a search tree, handling nodes with no children, one child, or two children. About 20 minutes.
Find it, then three cases
First find the node, going left for smaller keys and right for larger ones. Each call returns the root of its subtree after the deletion, so the parent simply stores what comes back.
When the node is found, look at its children. With no left child, the right child takes its place. With no right child, the left child takes its place. A leaf is covered by either rule, as the answer is then nothing.
if not node.left:
# replace by the right
return node.right- cases
- two children
Found 10 right at the root. It has two children, 4 and 15.
Two children
With two children, you cannot hand the node over to one child. Instead, find the smallest value in the right subtree by going left as far as possible. Copy that value into the node. The order is kept.
Then delete the copied value from the right subtree, where it is an easy case, since the smallest node has no left child. A key that is not in the tree just falls off the bottom, and the tree is unchanged.
m = node.right
while m.left:
m = m.left
node.val = m.valThe node to delete has a right child but no left child. What does the delete return in its place?
- AThe right child
- BNothing
- CThe smallest value on the right, copied in
Show the answer
The right child. The right child and everything below it keeps the order.
Delete a node from a search tree
Given the root of a binary search tree with different values and a key, delete the node with that value, if present, so that the tree remains a valid binary search tree, and return the root. If the node has two children, replace its value with the smallest value of its right subtree and delete that smaller node from the right subtree, so that the answer is unique.
root = [5, 3, 6, 2, 4, null, 7], key = 3 → [5, 4, 6, 2, null, null, 7]
0 ≤ number of nodes ≤ 10,000 · -100,000 ≤ node.val, key ≤ 100,000