Objectives

By the end of this chapter you should be able to:

• Compare and contrast three different types of removal in a binary search tree
• Implement removal from a binary search tree

Removing a node in a binary search tree

We've talked about a fair amount of functionality that we could implement on binary search trees. The biggest feature we haven't talked about yet is also one the most complex: removing a node. Let's examine the three situations in which a node is removed in increasing difficulty.

Removing a node with no children

The simplest possible scenario is that the node we want to remove has no children. In this case, all we need to do is ensure that the parent node of the node to be removed (if the node to be removed is not the root) is aware that the node has been removed.

Removing a node with one child

If we remove a node that has one child, we need to make sure to update the parent of the removed node and set its left or right property to be the single child of the removed node.

Removing a node with two children

Removing a node with two children is a bit more difficult, because after removal the tree still needs to satisfy the conditions of a binary search tree. Here are the steps involved:

• Find the node to remove
• Find the successor of the node
• Replace the node to be deleted with the successor

What is the successor? The leftmost child of the right child, if your current node has a right child. If the right child has no left child, the right child is your in-order successor. In other words, the successor is the unique node which can replace the node being removed and keep the subtree below the node being removed as a binary search tree.

It can be difficult to understand this algorithm by reading about it. It's much easier to understand with the help of some visual aids. You can practice with this algorithm by creating and removing nodes here.

Exercises

Complete Part III of the exercises here.