Delete a node with 2 children in a binary search tree

Question

Recently in class we learned how to delete a node from a binary search tree. Since in a binary search tree, each node can have at most 2 nodes, there are 3 cases of deletion.

Case 1: The node is a leaf node. In that case you can simply delete the pointer to that node and free up the memory for that.

Case 2: The node has one child. In that case, you can connect the parent and child of that node and delete the pointer to and from the node you want to delete.

Case 3: The node has 2 children. Here is where I'm having a bit of a problem. Let's assume we have the following example.

I want to delete the node "4". To do this, I go to the largest integer node on its right side, i.e. "5" and swap their values. So 4 becomes 5 and 5 becomes 5. The I can simply delete the node "5" and I'll be done. Is this approach correct or am I missing anything?

Answer 1

Your approach works in your example, but not in general. For example, if the node with key 5 also has a left child with key 4.5, it will not be correct because the resulting tree is not a binary search tree anymore.

You have to replace the node to be deleted (4) not with its right child (5), but with its successor in the key ordering, which is the least-valued node in its right sub-tree (in your example, that is indeed 5, but in my example it would be 4.5, not 5).