4 comments

a tech-savvy guy and a design buff... I was born with the love for exploring and want to do my best to give back to the community. I also love taking photos with my phone to capture moments in my life. It's my pleasure to have you here.

next post

## 4 comments

(2n)!/(n+1)! is the answer.

Catalan Number is for BST

no you are wrong the number of possible binary trees with 4 nodes is 14, but 2^4-4 is not 14.

I think total number of binary trees possible for n nodes is equal to Catalan number

C(n) = (2n)! / ((n+1)! * n!)

for n = 4, 14 binary trees are possible as given by catalan number. While 2^n-n = 12. for n=4

http://en.wikipedia.org/wiki/Catalan_number

Hi Amit,

For a binary “search” tree, the possible combinations is C(n), the Catalan number, we are talking about binary trees in general.

Thanks for the extra information though. :)

Comments are closed.