I am working on this project where I am required to find the theoretical proof for following.
I have a particular type of binary trees, where
1) each internal node will definitely have two children.
2) There are n leaf nodes and can be assumed in order 1 to n from left most to right most.
Now this is clear that there are multiple such trees. And I am performing tree rotation (https://en.wikipedia.org/wiki/Tree_rotation) operation in any of one internal node of the tree.
I was thinking that in any such type of tree with n leaf nodes there will be guaranteed n-1 internal nodes and total n-2 possible rotation moves. (The rotation is only valid if the rotated tree also has the two given properties i.e. an internal node with just left node as leaf node cannot be right rotated.)
I have tried various resources but couldn't find any proof for it. I have tried it myself but not able to reach to a solution. I'd be glad if someone can help me out here.
I could get to one possible proof, please see if it's correct.
There are 3 parts of the proof:
a) With these rotation moves, you can convert to any of the tree into a completely left branching tree, I have the proof for it and it's well known in graph theory.
b) Any rotation moves preserves the number of possible rotations in the tree. This is critical, I will prove it in the end.
c) In any left branching tree, out of total n-1 internal node, everyone except one can be right rotated. So total n-2 rotations.
All 3 together gives that total n-2 rotations possible.
Now the critical (b) part:
From the wikipedia image on the link (https://en.wikipedia.org/wiki/Tree_rotation), the number of rotations for subtrees A, B ,C remains the same and reverses for P and Q. So the total moves will remain same.
I can give more details for the above statement if required, but it's hard to write it here.