Convert binary tree using rotations

Question

While I was studying medium binary trees, I found a statement that any arbitrary n-node binary tree can be converted to any other n-node binary tree with a maximum speed of 2 * n-2. Is there any evidence for this? I found some evidence with asymptotic notation, but it was not so clear. I mean, can someone explain / show why this is true? And if he says that n- node is a binary tree, does it include the root?

Answer 1

This answer is from question 13.2-4 of the CLRS 3rd edition textbook.

Let be

LEFT = whole double double list tree on the left

RIGHT = an entire binary tree with a complete list of related links.

You can easily turn LEFT to the right in (n-1) turns.

  eg: n = 3 
     3 2 1
   2 to 1 3 to 2
 13

Proof: Since by definition each right rotation will increase the length of the rightmost path by at least 1. Therefore, starting from the rightmost path with a length of 1 (worst case), you will need no more than (n-1) turns to do it CORRECTLY .

Thus, you can easily conclude that any arbitrary binary tree form with n nodes can rotate in RIGHT inside (n-1) rotations. Let T_1 node you start with Let T_2 be the node you end with.

You can rotate T_1 to RIGHT inside (n-1) turns. By analogy, you can rotate T_2 to RIGHT inside (n-1) rotations.

Thus, To rotate T_1 to T_2, simply turn T_1 to the right, then reverse the rotation from ROTATION to T_2.

Therefore, you can do this at (n-1) + (n-1) = 2n-2 revolutions in the upper limit.

  Hope this helps! =)
 Soon Chee Loong, 
 University of toronto 

Answer 2

If an operator refers to binary trees, not BST trees, I believe that the operator is valid because there are no restrictions on the order of the nodes. And simple mathematical induction should prove the statement.