4 votes 4 votes How many different binary search trees can be constructed using six distinct keys? 256 128 132 264 DS binary-tree binary-search binary-search-tree + – Parshu gate asked Nov 27, 2017 Parshu gate 6.7k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply saxena0612 commented Nov 27, 2017 reply Follow Share The first few Catalan numbers for n=1, 2, ... are 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 3 votes 3 votes akshat sharma commented Nov 27, 2017 reply Follow Share or we can use formula 2nCn/(n+1) 12C6/7 12*11=132 4 votes 4 votes smsubham commented Feb 17, 2018 reply Follow Share good read: https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/ 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes We use the catalan number Cn = (2n)!/ (n+1)!*n! to find the number of binary search tree with n vertices. So in this case n = 6, Hence 12!/7!*6! = 132 Shivani Singhal answered Dec 24, 2017 Shivani Singhal comment Share Follow See all 3 Comments See all 3 3 Comments reply Sukannya commented Feb 17, 2018 i edited by Sukannya Feb 25, 2018 reply Follow Share It is same as binary trees with unlabelled nodes. 0 votes 0 votes joshi_nitish commented Feb 25, 2018 reply Follow Share @Sukannya # of BST with 'n' distinct nodes = # of unlabeled binary trees with 'n' nodes = $\frac{\binom{2n}{n}}{n+1}$ 1 votes 1 votes Sukannya commented Feb 25, 2018 reply Follow Share Ya, @joshi_nitish. It was a typo and my stupid habit of writing wrong ans inspite of knowing the correct ones... :) 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 132 BST trees are possible saipriyab answered Nov 27, 2017 saipriyab comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Get the no. of bst's possible with 'n' nodes 2nCn/n+1 (Catalyn no.) Shivam14chd answered Feb 24, 2018 Shivam14chd comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 12C6/6+1 12!/6!*6!*7 =>132 Ans is 132 Kirti11 answered Jun 15, 2020 Kirti11 comment Share Follow See all 0 reply Please log in or register to add a comment.