Deletion

Deletion is the least straightforward operation within a binary search tree and requires some careful maneuvering.

Let’s say we want to delete the 4 from this binary search tree:

First, we perform a search to find the 4. We won’t visualize this search again, since you’ve already got that down.

Once we find the 4, we can delete it in one step:

Well, that was simple. But let’s see what happens when we try to delete the 10:

We end up with an 11 that isn’t connected to the tree anymore. And we can’t have that, because we’d lose the 11 forever.

However, to solve this problem, we can plug the 11 into where the 10 used to be:

So far, our deletion algorithm follows these rules:

• If the node being deleted has no children, simply delete it.
• If the node being deleted has one child, delete the node and plug the child into the spot where the deleted node was.

Deleting a Node with Two Children

Deleting a node that has two children is the most complex scenario. Let’s say we want to delete the 56 in this tree:

What are we going to do with its former children, 52 and 61? We can’t move both of them to where the 56 was. This is where the next rule of the deletion algorithm comes into play:

• When deleting a node with two children, replace the deleted node with the successor node. The successor node is the child node whose value is the least of all values that are greater than the deleted node.

That was a tricky sentence. To put it in other words: if we were to put the deleted node and all of its descendants in ascending order, the successor node would be the next number after the one we just deleted.

In this case, it’s easy to figure out which node is the successor since the deleted node had only two descendants. If we put the numbers 52-56-61 in ascending order, the next number after 56 is 61.

Once we find the successor node, we plug it into where the deleted node was. So we replace the 56 with the 61:

Finding the Successor Node

How does the computer find the successor node? This can be tricky when we delete a node high up in the tree.

Here’s the algorithm for finding the successor node:

• Visit the right child of the deleted value, and then keep on visiting the left child of each subsequent child until there are no more left children. The bottom value is the successor node.

Let’s see this again in action in a more complex example. Let’s delete the root node:

We now need to plug the successor node into where the 50 was and turn it into the root node. So let’s find the successor node.

To do this, we first visit the right child of the deleted node, and then keep descending leftward until we reach a node that doesn’t have a left child:

It turns out that the 52 is the successor node.

Now that we’ve found the successor node, we plug it into the node we deleted:

And we’re done!

Successor Node with a Right Child

We haven’t accounted for one case yet, though, and that’s where the successor node has a right child of its own. Let’s re-create the preceding tree but add a right child to the 52:

In this case, we can’t simply plug the successor node—the 52—into the root, since we’d leave its child of 55 hanging. This leads us to one more rule for our deletion algorithm:

• If the successor node has a right child, after plugging the successor node into the spot of the deleted node, take the former right child of the successor node and place it where the successor node used to be.

That was another tricky sentence, so let’s walk through the steps.

First, we plug the successor node (52) into the root. This leaves the 55 dangling without a parent:

Next, we place the 55 in the spot where the successor node used to be, which is the left child of the 61:

Successor Node is a Right Child

It can sometimes happen that the successor node is itself a right child. And sometimes this successor node can have a right child of its own. For example, in the following tree, if we delete the 3, the 4 becomes the successor node, since the 4 has no left children:

Here, when we plug the successor node into the spot where the deleted 3 was, we don’t make the 5 dangling and reattach it elsewhere. Instead, we simply keep the 5 as the 4’s right child.

And now we’re really done.

The Complete Deletion Algorithm

Putting all the steps together, here is the algorithm for deletion from a binary search tree:

• If the node being deleted has no children, simply delete it.

• If the node being deleted has one child, delete the node and plug the child into the spot where the deleted node was.

• When deleting a node with two children, replace the deleted node with the successor node. The successor node is the child node whose value is the least of all values that are greater than the deleted node.

• To find the successor node: visit the right child of the deleted node, and then keep on visiting the left child of each subsequent child until there are no more left children. The bottom node is the successor node. If the deleted node’s right child has no left children, the deleted node’s right child itself becomes the successor node.

• If the successor node has a right child (and the successor node was itself a left child of its parent), after plugging the successor node into the spot of the deleted node, take the former right child of the successor node and turn it into the left child of the former parent of the successor node.

Code Implementation: Binary Search Tree Deletion

Here’s a Python implementation of deletion from a binary search tree. The primary method here is delete, which in turn relies on a helper method called replace_with_successor_node:

That’s a decent amount of code, but we’ll walk through it step by step.

In contrast with search and insertion, we wrote the deletion code without recursion. While we could have written the deletion method recursively, I find that the recursive code for deletion is considerably more difficult to grasp. Instead, we use a loop to move about the tree.

Let’s begin by walking through the delete method.

When we call this method, we pass in the value we’d like to delete (value_to_delete) as well as the root node of the tree (node).

At first, we set three variables:

The current_node initially points to the root but will be updated as we move down the tree looking for the value we are to delete. The parent_of_current_node is, as the name implies, the parent of the current_node. The reason we need to track this will become apparent later on. Finally, the node_to_delete will eventually point to the node we’ll be deleting, but until we find that node, this variable is set to None.

We then begin a loop that searches for the value_to_delete within the tree. This is essentially a search operation, but again, this time we use iteration instead of recursion:

This snippet moves down through the tree, updating current_node as we go, searching for the value_to_delete. If we don’t find it, which will be the case if the value is not present in the tree, the loop will terminate on its own because current_node will be None.

If, however, we do find the value_to_delete, we declare the current_node to be the node_to_delete and break out of the loop. Note that we also keep track of the parent_of_current_node, which is now the parent of the node we’ll be deleting.

Next, we have this snippet:

This returns None if the value we’d like to delete isn’t even in our tree to begin with.

The remainder of this method performs the actual deletion. We first handle the most complex case, where the node we’re deleting has two children:

Here, we outsource the heavy lifting to the replace_with_successor_node helper method, which we’ll analyze soon. In the meantime, though, let’s move on.

Next, we handle the case in which the deleted node has 0 or 1 children:

Here, we first set a new variable called child_of_deleted_node, which will represent the deleted node’s child. In a case where the deleted node had no children, this variable will be set to None. This variable is crucial, for when we delete our node_to_delete, we need to place its child in the spot where the deleted node used to be.

And that’s exactly what the code above does in the two elif clauses. It determines whether the deleted node was a left or right child of its parent, and attaches the child_of_deleted_node to the deleted node’s parent accordingly.

The first clause in the if statement handles the case where we’re deleting the root node. To ensure that we mark the deleted root’s child as the new root, we overwrite the root with its child.

This brings us to the final line of our method, which simply returns the deleted node in case we may want to use it for some other purpose:

Let’s now return to the case where the deleted node had two children. Our previous code called the helper method replace_with_successor_node, so let’s walk through that now.

When calling this method, we pass in the node that we’ll be deleting, which will be called node.

Next, we identify the successor node using the following code:

Here, we begin at the deleted node’s right child, and then move down the tree following left children until we can’t go any further. That bottom node is our successor node. We also keep track of the successor node’s parent.

However, in the case that the successor node happens to be the deleted node’s right child (which occurs when the deleted node’s right child has no left children), we simply plug the successor node into the spot where the deleted node was. If this is the case, this is all we need to do. But if the successor node is a left child of its parent, we move on.

Next, we remove the successor node from its spot:

Our code deals with two possible cases. The second case (in the else clause) is the simpler case, which is when the successor node had no children. In that case, we wipe away the successor node by replacing it with None.

In the more complex case, where the successor node has a right child, we place that right child in the spot where the successor node used to be.

We’ve successfully removed the successor node from the tree, but there’s one more critical step. Remember we didn’t initially set out to delete the successor node. Our entire goal was to delete the node from higher up in the tree.

To do that, we plug the successor node into the spot of the node we’re deleting:

Note that we don’t plug in the actual successor node; instead, we simply use its value to overwrite the value of node, effectively deleting node.

And that’s it! It was a journey, but we did it.

The Efficiency of Binary Search Tree Deletion

Like search and insertion, deleting from trees is also typically O(log N). This is because deletion requires a search plus a few extra steps to deal with any hanging children. Contrast this with deleting a value from an ordered array, which is O(N) due to shifting elements to the left to close the gap of the deleted value.