Understanding recursive deletion

Just like insertion, deleting a node with the given value from a binary search tree can be implemented by piggybacking on the search algorithm we learned earlier. However, unlike insertion, deleting a node from a binary search tree is more complex as we must ensure the tree follows the binary search property after the deletion.

Algorithm

Deleting a node from a binary search tree is a two-step process.

• Step 1: Search the node to be deleted
• Step 2: Delete the node

We search for the node to be deleted using the search algorithm we learned earlier. However, deleting the node once we find it is not straightforward, as there are three different cases we need to consider. Let us look at these cases.

1. Node to be deleted is a leaf node

This is the most straightforward case of deletion. If the node to be deleted is the leaf node, we can search for the node using the search algorithm we learned earlier and delete the node.