0
$\begingroup$

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: enter image description here

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?

$\endgroup$
  • $\begingroup$ Welcome to CS@SE. I'm not sure I get what you want to express using 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$ – greybeard Dec 17 '19 at 2:25
2
$\begingroup$

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).

node x to be deleted has two children, swap with predecessor p

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.

deletion of node x with single child

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is the most accurate explanation I've seen. Thank you! Now it is clear $\endgroup$ – Oleksandr Dec 16 '19 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.