How to delete a node from BST tree with 2 chidren?

Question

I googled, read several tutorials and watched several BST node deletion algorithm explanations before posting this question. For some reason, I cannot find a complete explanation of BST node deletion algorithms.

I've found 4 algorithms to remove the node with 2 children from Binary Search Tree:
1) Find the smallest node from right sub tree and replace it with the node which we want to delete.
2) Find the biggest node from left sub tree and replace it with the node which we want to delete.
3) Find the deepest leftmost node from the right sub tree and replace it with the node which we want to delete.
4) Find the deepest rightmost node from the left sub tree and replace it with the node which we want to delete.

Apparently, none of those algorithms works for the next use case (most likely because I am missing or don't understand something). The use case is to remove element 5 from the next tree:

For the first algorithm we would chose element 6 and would lose its right sub tree. For the second algorithm we would chose element 4 and would lose its left sub tree. For the 3rd algorithm we would chose element 7 and which would violate BST rules. For the 4th algorithm we would chose element 3 which would also violate BST rules.

What is the right algorithm for such a use case?

Answer 1

You are right, in BST usually the case where a node has two children is reduced to the case where a node has one child.

Consider a node with two children. Swap this node with its predecessor in the BST (that is the rightmost node in the left subtree), or --totally symmetric-- swap with the successor (the leftmost node in the right subtree).

The node to be removed now has at most one child (in case we went for the predecessor it cannot have a right child). If it has no children we delete the node, and we are done.

In case the node has a single child, we remove the node and replace it by its subtree. We again obtain a BST.

In your example we want to remove 5 and swap it with its predecessor 4. Now 4 is in the root, and 5 has left child 3. Finally we remove 5 and put its child 3 on its place. Now 3 is the right child of 2.

PS. This method is sometimes called "deletion by copying", because values are copied from one node to another. Some do not approve of this process for two reasons. First copying might be an expensive operation, and second references are lost (if another datastructure points to a node with a certain value). Instead one only changes the pointers.