Deletion procedure for a Binary Search Tree

manpreet Best Answer 3 years ago

Consider the deletion procedure on a BST, when the node to delete has two children. Let's say i always replace it with the node holding the minimum key in its right subtree.

The question is: is this procedure commutative? That is, deleting x and then y has the same result than deleting first y and then x?

I think the answer is no, but i can't find a counterexample, nor figure out any valid reasoning.

EDIT:

Maybe i've got to be clearer.

Consider the transplant(node x, node y) procedure: it replace x with y (and its subtree). So, if i want to delete a node (say x) which has two children i replace it with the node holding the minimum key in its right subtree:

y = minimum(x.right)
transplant(y, y.right) // extracts the minimum (it doesn't have left child)
y.right = x.right
y.left = x.left
transplant(x,y)

The question was how to prove the procedure above is not commutative.