Number of binary search trees possible with nodes equal to or less than n

Question

I know total number of distinct BST's possible with N distinct nodes are given by Catalan formula . Which is described in this question at SO.

But how can we use it to find all the BSTs less then or equal to n nodes(N distinct nodes)?

for e.g.

For N=3

 Possible numbers of BST's are 14.

 9 Shown in Picture below for less than 3.
 5 for N=3 which can be obtained from Catalan formula.

BST FOR N 3

What is the approach to solve it? I need only algorithmic explanation.

that will not be correct. `catalanFormula(1)=1,catalanFormula(2)=2,catalanFormula(3)=5` sum of which gives 8 for 3. But answer is 14. — user3594106, Jun 04 '14 at 18:09
Its a live contest answers. why are u in such hurry for answers. Answers are anyway published after contests — coder hacker, Jun 05 '14 at 03:55

score 0 · Accepted Answer · answered Jun 04 '14 at 18:18

0

The mathematical formula shall be:

summation ( C(n,i) * Catalan(i) ) {i = 1 to n}

Where C(n,i) = n! / ( i! * (n-i)! )

You can choose i nodes out of a possible n nodes in C(n,i) ways. After choosing those i nodes, form the BSTs in Catalan(i) number of ways.

answered Jun 04 '14 at 18:18

Abhishek Bansal

Yes, but you should note that the number increases atleast exponentially (possibly at a factorial rate). – Abhishek Bansal Jun 04 '14 at 18:25

1 Answers1