You know how to create a binary search tree, and through that process you also should know how to add items to a BST. In this guide we're going to examine how to remove items from a binary search tree.

As you may imagine it's slightly more complex to remove items from BSTs than to add them. I'd love to give you a nice and easy illustration for deleting elements, such as pulling an apple off a tree. However tree deletion isn't quite that straightforward.

Real World Example of Removing Nodes from a BST

Because the nodes in a binary search tree are connected, along with having the requirement that parent nodes reference their respective child nodes, the concept of deletion have to take these references into account.

Let's return back to our example of building a mapping application. If your algorithm had the goal of generating a route for users to navigate around the country, what would have to happen if a detour occurs? For example, if you application generates a route that takes the user from California to New York City, we can assume that a few stops along the way would be:

• Denver, CO
• Lincoln, NE
• Des Moines, IA

Now what would happen if our routing system would find out that Lincoln, NE had a nasty blizzard and wasn't drivable? Our application would have to delete that location.

However deleting the location isn't enough to satisfy the algorithm requirement. Our system will also have to re-route the user so they're not left stranded. Can you imagine how bad the Google Maps application would be if it told you tough luck each time a detour happened?

How to Delete a Node from a Binary Search Tree

So let's review what needs to occur in order to delete a node from a binary search tree:

1. If a node has no children it can simply be removed from the tree. This is an easy scenario.
2. When a node has a single child, the parent node simply references the deleted node's child. This is also an easy scenario since you are only required to change the reference to a known node and no tree re-organization is required.
3. Lastly, when you have to delete a node that has two children, the deletion process becomes more challenging.

In looking at this example binary search tree, let's imagine that we have to delete the 33 node. This node has two children: 27 and 42. And these child nodes have their own respective child nodes. The workflow that we'll follow to remove the 33 node is as follows:

1. We'll perform a search to find the lowest value in the right sub tree. In this case that value is 37. The key with this step is finding the lowest value in the right subtree, which means that it will be a node that does not have any child nodes itself.
2. Next we duplicate the value we've selected, so the 37 value will replace the 33 node.
3. Lastly we perform the straightforward deletion of the 37 node.

And that's it!

Summary

You now know how to delete nodes from a binary search tree. Including how to remove nodes in each of the three scenarios that deletions will take place. If you follow workflow outlined in this guide you'll discover that removing nodes from a binary search tree is relatively straightforward.

What's Next?

In the next guide we'll examine the tree traversal process.