2
$\begingroup$

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:

1,2,3

1,3,2

2,1,3

2,3,1

3,1,2

3,2,1

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.

$\endgroup$
  • $\begingroup$ Can you deduce your answer from the number of possible BSTs on $n$ elements? $\endgroup$ – Yuval Filmus Dec 31 '17 at 15:24
  • $\begingroup$ Is it somehow related to Catalan number? $\endgroup$ – Rajeev Pandey Dec 31 '17 at 15:30
  • $\begingroup$ This is very likely. $\endgroup$ – Yuval Filmus Dec 31 '17 at 17:17
  • $\begingroup$ Why is your answer 2 (for n=3)? In that case you have five possible binary trees and six permutations? Are you looking for the trees that have a unique permutation? $\endgroup$ – Hendrik Jan Jan 1 '18 at 13:45
  • $\begingroup$ No I'm looking for trees that have same structure. 2,1,3 and 3,1,2 have same structure $\endgroup$ – Rajeev Pandey Jan 1 '18 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.