32 votes 32 votes How many distinct BSTs can be constructed with $3$ distinct keys? $4$ $5$ $6$ $9$ DS gateit-2008 data-structures binary-search-tree normal + – Ishrat Jahan asked Oct 29, 2014 • edited Dec 21, 2017 by kenzou Ishrat Jahan 12.6k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Satyajeet Singh commented Jan 30, 2018 reply Follow Share distinct BSTs can be constructed with 33 distinct keys here keys are distinct means we have to consider the case of the labelled tree . and as per the link https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/ answer should be (2n)! / (n+1)! i guess if the question was asking for distinct BST for n nodes(unlabelled or similar nodes) then it would be catalan no . Please check . 5 votes 5 votes Abhishek Rauthan commented Mar 5, 2023 reply Follow Share if in the questions instead of binary search tree,how many no. of binary tree with 3 distinct node then it would be (2n C n)*n! which is 5*6=30 1 votes 1 votes Saitama904 commented Sep 22, 2023 reply Follow Share Can anyone draw all 5 bst 0 votes 0 votes Arjun commented Sep 22, 2023 reply Follow Share Why not try it? :) 1 votes 1 votes Please log in or register to add a comment.
Best answer 44 votes 44 votes For number of distinct BSTs with $n$ nodes we apply the formula $\dfrac{C(2n,n) }{n+1}$ $n=3$ here, so $C(6,3)=20$ So, $\frac{C(2n,n)}{n+1} =20/4=5$ Answer is $\mathbf{5}$ REF :- https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/ Correct Answer: $B$ Abhimanyu Kumar answered Nov 20, 2014 • edited May 4, 2019 by Naveen Kumar 3 Abhimanyu Kumar comment Share Follow See all 4 Comments See all 4 4 Comments reply R Prabhakar 1 commented Dec 14, 2017 reply Follow Share Can u explain how C(2n,n) will work 1 votes 1 votes Lakshman Bhaiya commented Feb 2, 2018 reply Follow Share @ R Prabhakar 1 Yes and you can also check https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/ 1 votes 1 votes talha hashim commented Jan 23, 2019 reply Follow Share https://en.wikipedia.org/wiki/Catalan_number 1 votes 1 votes PratikDey0316 commented Dec 2, 2020 reply Follow Share https://gateoverflow.in/485/gate2008-62 Why can’t we solve this question in a similar way as it is solved in the above link? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Option B is the answer Vasudevarnabmessi answered Mar 18, 2023 Vasudevarnabmessi comment Share Follow See all 0 reply Please log in or register to add a comment.