5

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?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
fhuseynli
  • 630
  • 3
  • 12
  • 26
  • 2
    That doesn't sound right, since rotations don't change the order of the nodes. Are you sure there isn't some other restriction? – Beta Oct 28 '13 at 01:18
  • 1
    http://repository.cmu.edu/cgi/viewcontent.cgi?article=2663&context=compsci maybe you want to reference this paper. – notbad Oct 28 '13 at 09:47

2 Answers2

4

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
Chee Loong Soon
  • 3,601
  • 3
  • 17
  • 21
1

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.

Pandrei
  • 4,843
  • 3
  • 27
  • 44