Number of possible rotations. Binary search tree

Question

Why there are exactly n-1 possible rotations on a binary search tree?

Answer 1

In the binary tree there are n nodes. We know that the order of the nodes cannot be changed. Each of the nodes are labelled with a number {1...n}. Lets assume n=4 and the label current root of the tree is 1. how many other possible roots can you have?

The only alternatives are 2,3,4 Therefore on the tree, there are only N-1 more roots the tree can have and only N-1 unique rotations. May not be a theoretical explanation but I hope this helps you visualize it.

Answer 2

rotations can only be applied on left edge or right edge. In n nodes BST there is n-1 edges hence n-1 rotations are possible.

Answer 3

I think this property can be proved by recursion.

For n = 1, the property is true.
assume that this is true for all binary search tree with k nodes such as k <= n
For a bst A with n + 1 nodes:
nbRotation (A) = 2 + nbRotation (left(A)) + nbRotation (right(A))
assume that the size of the left(A) = p and the size of the right(A) = m then 
nbRotation (left(A)) = p-1 and the nbRotation (right(A)) = m-1
So nbRotation(A) = 2 + m-1 + p-1 = m + p = n