Deletion in Binary Search Tree, node with 'right child' only

Question

I was trying to code deletion of node in BST and am now bit confused about the case where node has right_child only.

Most of the algorithms handle 4 cases:

• If it's the leaf node, delete it

• If the node has only left_child, promote it

• If the node has only right_child, promote it

• If node has 2 children, replace the value with inorder_successor of node, and delete the successor

When I was trying to code it, I handled following 3 cases:

• If it's the leaf node, delete it

• If the node doesn't have right_child, promote the left child

• Else, replace the value with the inorder_successor of the node, and delete the successor

Eventually, the resulting BST will be different for the following case:

- With the way I delete node with right child only:

       1        Delete(1)      3
         4     ----------->      4
       3

- The way other algos suggest:
       1        Delete(1)        4
         4     ----------->    3
       3

I can't seem to find if there is anything wrong with the way I am deleting it

Sure, the BST could be more right-skewed and more deletions would happen recursively, but the BST invariant is still intact, right ?

There was some discussion here and here but there is no accepted answer

Answer 1

When I was trying to code it, I handled following 3 cases ...

It is more natural to add a case:

• If it's the leaf node, delete it
• If the node doesn't have right_child, promote the left child
• If the node doesn't have left_child, promote the right child
• Else, replace the value with the inorder_successor of the node, and delete the successor

This limits the use of the algorithm in the last bullet point to the very minimum, as that is the more costly one.

However, there is not just one way to get a valid BST, so even if you skip that case and use the "Else" algorithm for it, you still will get a valid BST.