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?
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