No. of Binary trees

Question

FIve nodes labelled 1,2,3,4,5 are used to construct different binary trees. How many such binary trees can be constructed whose preorder traversal is 1,2,3,4,5 ?

Comments

It should be 42..

Plz check :

http://cs.stackexchange.com/questions/55683/how-many-number-of-different-binary-trees-are-possible-for-a-given-postorder-or

Answer 1

No. of binary trees for  a particular preorder/ionorde /postorder can be calculated using formula Cn=1n+1(2n n)

here n=5

so answer will be 42

Comments

What is the formula and it came ?

---

It is the nth Catalan number i.e

Cn = (2n)! / ((n + 1)!n!)