if I have two binary search trees with the same keys(n keys) but not identical, I can get from the first tree to the other by maximum n tree rotations. how can I prove it? for example I can get from tree 1 to tree 2 by one rotation:
2026-03-28 13:22:57.1774704177
binary search tree rotations
109 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
This is probably the same thing as the famous problem posed by Daniel Sleator, Robert Tarjan, and William Thurston asking for the diameter of the associahedra or the diameter of the rotation graph on plane binary trees.
The correct diameter is rather $2n - 2$.
This has been solved by Pournin in 2012 in the language of flips of triangulations, see his article.