patternMinor
Number of different binary search trees storing n distinct keys?
Viewed 0 times
distinctnumbersearchtreesdifferentkeysbinarystoring
Problem
How many different binary search trees are possible that store the values 1,2,...,n ?
So far I found a recursive formula for the number (by case distinction what's at the root):
$ T(n) = 2T(n-1) + \sum_{i=2}^{n-1}T(i-1)T(n-i), n > 1 $ and $ T(1) = 1 $
But I have no idea how to solve this recursion. Our task was only to find the recursion and I believe this to be a correct solution. But I am very interested in a closed formula of it. Can anyone link me to some resources/books or give a general hint on how it can be solved?
So far I found a recursive formula for the number (by case distinction what's at the root):
$ T(n) = 2T(n-1) + \sum_{i=2}^{n-1}T(i-1)T(n-i), n > 1 $ and $ T(1) = 1 $
But I have no idea how to solve this recursion. Our task was only to find the recursion and I believe this to be a correct solution. But I am very interested in a closed formula of it. Can anyone link me to some resources/books or give a general hint on how it can be solved?
Solution
The solution to your recurrence is
$$ T(n) = \frac{(2n)!}{n!(n+1)!}, $$
also known as the Catalan numbers. The quickest way to find this is by computing a few elements of the sequence and using the OEIS to identify the sequence.
$$ T(n) = \frac{(2n)!}{n!(n+1)!}, $$
also known as the Catalan numbers. The quickest way to find this is by computing a few elements of the sequence and using the OEIS to identify the sequence.
Context
StackExchange Computer Science Q#66617, answer score: 4
Revisions (0)
No revisions yet.