# has deleting node in a binary search tree Displacement feature?

I am developing an academic project about graph and tree theory.I searched a lot but I didn't find a clear answer. In a part of project we want to delete some nodes from tree for example we want to delete nodes A and B.I want to know that if we Delete A and then B does It give us exactly the same tree that We will produce when We Delete B and then A and if yes is there any proof or anything that can make sure us about that.

-
What do you mean exactly by deleting? What kind of search tree are you using (balanced?, keys in all nodes or just the leaves?) –  A.Schulz Nov 25 '12 at 7:49
a simple binary search tree keys in all nodes(include leaves).being balance is not required. –  CoderInNetwork Nov 25 '12 at 12:27
deleting means that for example detele('4') removes node with key 4 from our tree. –  CoderInNetwork Nov 25 '12 at 12:30

finally i will find the answer! Deletion (in general) is not commutative. Here is a counterexample:

    4
/ \
3   7
/
6


What if we delete 4 and then 3?

When we delete 4, we get 6 as the new root:

   6
/ \
3   7


Deleting 3 doesn't change the tree, but gives us this:

  6
\
7


What if we delete 3 and then 4?

When we delete 3 the tree doesn't change:

 4
\
7
/
6


However, when we now delete 4, the new root becomes 7:

  7
/
6


The two resulting trees are not the same, therefore deletion is not commutative.

reference and more details : http://stackoverflow.com/questions/2990486/deletion-procedure-for-a-binary-search-tree

-