#### Deletion procedure for a Binary Search Tree

##### Replies

###### Alice Davidson

User

( 5 months 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.

Ra
04-Sep-2019

2 Replies

Ra
05-Sep-2019

2 Replies

11-Sep-2019

0 Replies