Binary tree transformation using rotations

Question

While i was studying for midterm about binary trees, i found a statement that any arbitrary n-node binary tree can be transformed into any other n-node binary tree with at most 2*n-2 rotations. Is there any proof for that? I found some kind of proof with asymptotic notations but it was not that clear. I mean could someone explain/show why it is true? And if it says that n-node binary tree, does it include the root?

Windbound

That doesn't sound right, since rotations don't change the order of the nodes. Are you sure there isn't some other restriction? – Sinclair

repository.cmu.edu/cgi/… maybe you want to reference this paper. – Killerdiller

Answer 1

This answer is from CLRS 3rd Edition textbook question 13.2-4.

Let

LEFT = an entire left linked list binary tree

RIGHT = an entire right linked list binary tree.

You can easily rotate LEFT to RIGHT in (n-1) rotations.

e.g: n = 3 
    3              2              1
  2     to        1  3   to        2
1                                    3

Proof: Since by definition, each right rotation will increase the length of the right most path by at least 1. Therefore, starting from right most path with length 1 (worst case), you need at most (n-1) rotations performed to make it into RIGHT.

Thus, you can easily conclude that any arbitrary shape of binary tree with n nodes can rotate into RIGHT within (n-1) rotations. Let T_1 be node you begin with Let T_2 be node you end with.

You can rotate T_1 to RIGHT within (n-1) rotations. Similarly, You can rotate T_2 to RIGHT within (n-1) rotations.

Therefore, To rotate T_1 into T_2, simply rotate T_1 into RIGHT , then do the inverse rotation to rotate from RIGHT into T_2.

Therefore, you can do this in (n-1)+(n-1) = 2n-2 rotations in upper bound.

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

Pyrrha

Answer 2

If the statement refers to binary trees not BST trees I think the statement is valid, since there is not restriction about the order of the nodes. And a simple mathematical induction should prove the statement.

Hoyos