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?
replace [the appropriate node] with the node which we want to delete
. Can you please edit into your post, too, where you found 3)&4)? $\endgroup$