educative.io

Educative

Deletion of a Parent Node with Two Children

A reader sent us the following query:

When we deleting the parent node wiht two children, could we 1. Starting by traversing the left subtree of the soon-to-be delted parent node in such a way that you reach the right-most value - the value that will appear to be the biggest value in the whole subtree. 2. Replace the value of the node, found in the last step, with the parent’s node value. 3. Finally, delete the leaf node.

Hi,

This is Fatimah Abdullah from Educative. Thank you for reaching out to us!

In response to your query, yes, this can also be done. The algorithm mentioned in the lesson traverses the right subtree to find the smallest value. However, the approach you have mentioned is also correct and will result in a valid binary search tree. For example:

binarysearchtree

In the BST shown in the illustration, if we delete node having data=6, we can replace it with either 5 or 7. Both of these approaches will produce a valid BST. I hope this explanation helps.

Thank you for reaching out to us with your query. If you have any further questions or concerns, feel free to get in touch.

Best Regards,
Fatimah Abdullah | Developer Advocate
Educative