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 would be exponential number of such possible trees which have theses two properties.
If I start from any random tree and randomly sample one of the internal node perform one of the two operations Left Rotate or Right Rotate (https://en.wikipedia.org/wiki/Tree_rotation), randomly. Is it possible to start from any random to tree to any other tree in the search space.
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.
First show that all trees with same number of leaf nodes have same number of internal nodes. That is shown by checking how many leaf nodes has a tree with I internal nodes. With I internal nodes, there are 2*I edges. I-1 of these edges connects internal nodes, so I+1 edges are left for leaf nodes. So, tree with n leaf nodes, has n-1 inner nodes.
To see that one tree can be transformed to the other tree, it is enough to transform both trees to some 'base' tree. E.g. let A be tree where every internal node (except last) has on left side leaf and on right side internal node. It is more like a path :-) To transformed any tree to A only right rotations are needed, and that is easy to find order nodes how to do rotations. To transform T1 to T2 it is enough to transform T1 to A, and than by reverse list of rotations A to T2.