Possible no. of BST's from given no. of nodes

Pls explain how to find these!! 

Q1. Find the number of trees that are possible, if we construct a BST by successively inserting 5 distinct items into an initially empty tree. 
Q2. The binary tree can be created out of 5 distinct nodes are?? 

I am getting 120 and (120)2 applying my tiny brain!! Pls explain where i am makiing mistake??

nikhil prasad @itsnix
4 Feb 2017 02:51 pm

It should be 42...By applying formula...2nCn/n+1

Shraddha @shraddhagami
4 Feb 2017 04:55 pm


answer of Que1 and Que2 is 42

Ashish Kumar Goyal @dashish
5 Feb 2017 11:26 am
@shraddhagami @itsnix
first one is correct but second one's answer is 5040..
Pls explain how to find?? (pls no more formulas).......
Shraddha @shraddhagami
5 Feb 2017 11:45 am


If nodes are labeled then answer is 5040(calculating 42*5!)

Distinct nodes are mentioned therefore 5040

Ashish Kumar Goyal @dashish
5 Feb 2017 12:00 pm


Pls also explain the first one.. How is it comming?? how 2nCn/n+1??

Shraddha @shraddhagami
5 Feb 2017 01:33 pm


No. Of binary search tree is same as No. Of binary tree with unlabeled n nodes.(if nodes are distinct in BST)

Ashish Kumar Goyal @dashish
5 Feb 2017 03:57 pm

I need to know about the first one (Q1).. where order is fixed!.....

Shraddha @shraddhagami
5 Feb 2017 04:08 pm

If order is fixed then only 1 tree is possible.


Ashish Kumar Goyal @dashish
5 Feb 2017 05:03 pm

order is fixed but numbers are not fixed!!