educative.io

Educative

Deletion of a parent node, when it's right subtree's smallest element is a parent too

I think there is a missing scenario about deletion of a parent node with 2 children.
When the right subtree’s smallest element is also a parent. Which means that right subtree’s top element doesn’t have left child.
In the above case, after step #2 of deletion algorithm, the replaced node (soon-to-be deleted) is a parent node with one child instead of a leaf node.

After this step, it will be handled as a deletion of a parent node with 1 child.

Hope i made myself clear.

1 Like