Deleting nodes from a binary search tree

Question

I understand the idea when deleting a node that has two subtrees: I "erase" the node's value and replace it with either its predecessor from the left subtree's value or its successor from the right subtree's value, and then delete that node.

However, does it matter if I choose the successor from the right subtree or the predecessor from the left subtree? Or is either way valid as long as I still have a binary search tree after performing the deletion?

Answer 1

Both ways to perform a delete operation are valid if the node has two children.

Remember that when you get either the in-order predecessor node or the in-order successor node, you must call the delete operation on that node.

Answer 2

It doesn't matter which one you choose to replace. In fact you may need both.

Look at the following BST.

    7    
   / \    
  4   10    
 / \   /    
1   5  8
 \
  3

To delete 1, you need to replace 1 with right node 3.

And to delete 10, you need to replace 10 with left node 8.