Delete Node in BST

excerpt: This covers delete node implementation in a binary search tree.

Delete Node Implementation

The first step in deleting a node is to find the node to be deleted. The previous article covered [how to search a node]({% post_url 2021-04-14-bst-search %}) in a binary search tree. The second step depends on the position of the target node in the tree.

The simplest case is deleting a leaf node, where we delete the leaf node and the BST remains as BST. For example, if the node 89 is deleted from the tree, the result is the tree shown in the diagram.

If the target node has only one child, the node can be replaced with its child. For example, if node 71 is deleted from the tree, the result is the tree shown in the diagram.

The complicated case arises when the target node has two children. In this case, the general stragety is to replace the node with its left child, but this leads to two subcases.

The first subcase occurs when the target node’s left child has no right child, the target node can be replaced with its left child. For example, if node 21 is removed from the tree, the resulting tree is as shown in the diagram.

The second subcase occurs when the target node has two children and its left child has a right child. In this case, search down the tree to find the rightmost node below the target node’s left child. If that node has no children, replace the target node with it. If that node has a left child, replace it with its left child and then replace the target node with the rightmost node.

For example the diagram shows deleting node 35. This node has two children and its left child 17 has a right child 24. The first step is to move down from the left child 17 as far as possible by following right links. In this example, this leads to node 24, but in general that rightmost child could be farther down the tree.

The rightmost node is replaced with its child and then replaces the target node with the rightmost node. In this example, the node 24 is replaced with node 23 and then node 35 is replaced with node 24, resulting in the tree shown in the diagram.