If I have numbers ranging from 1 to n, and I generate all the permutations of these numbers. Now, I create Binary search tree from these permutations. For a value n i want to know how many BSTs would have same structure. for example for n=3; we have:
In this 2,1,3 and 2,3,1 produce same BST. So for 3 answer is 2.
I have figured out that if I take 3 numbers, and the root is less than one number and greater than other, then the sequence produced is same. ie. for n=9
2,1,3, 5,4,6 8,7,9 and 2,3,1 5,6,4 8,9,7 produce same BST.