edited by
2,005 views
10 votes
10 votes
Q1. How many binary search trees possible with $11$ distinct key?

Q2. How many binary search trees possible with $11$ un-labelled nodes?

Q3. How many binary search trees possible with $11$ labelled nodes?

Q4. How many binary trees possible with $11$ distinct key?

Q5. How many binary trees possible with $11$ un-labelled nodes?

Q6. How many binary trees possible with $11$ labelled nodes?
edited by

1 Answer

Best answer
6 votes
6 votes

Q1) How many binary search trees possible  with  11 distinct key?

Ans) nth Catalan Number $\frac{1}{n+1}\binom{2n}{n}$ = $\frac{1}{11+1}\binom{22}{11}$ = 58786

Q2)How many binary search trees possible with 11 un-labeled nodes?

Ans)  How can we create BST without any key or label? 

Q3)How many binary search trees possible with 11 labeled nodes?

Ans) Binary search trees have keys and they are always labeled. If nodes are different then answer is same as above and if  all               nodes are same then check answer of 5th question. 
         https://www.geeksforgeeks.org/how-to-handle-duplicates-in-binary-search-tree/

Q4) How many binary trees possible with 11 distinct key?

Ans) It is a binary tree and it just have one rule that a parent node can have at max 2 children. (No restrictions like BST's)
        $\frac{(2n)!}{(n+1)!}$ = $\frac{(22)!}{12!}$
        https://gatecse.in/number-of-binary-trees-possible-with-n-nodes/ (check the 1st answer)

Q5) How many binary trees possible with 11 un-labeled nodes?

Ans) nth Catalan Number $\large \frac{1}{n+1}\binom{2n}{n}$ = $ \large \frac{1}{11+1}\binom{22}{11}$  = 58786

Q6) How many binary trees possible with 11 labeled nodes?

Ans) If all labels on nodes are distinct then total numbers of binary trees =  $\frac{(22)!}{12!}$

but in case there are k nodes which are having the same label then,

number of binary trees =  $\large \frac{(22)!}{12! \ k!}$

edited by

Related questions

1 votes
1 votes
1 answer
1
pradeepchaudhary asked Aug 19, 2018
19,106 views
8. What are the worst case and average case complexities of a binary search tree?a) O(n), O(n)b) O(logn), O(logn)c) O(logn), O(n)d) O(n), O(logn)
1 votes
1 votes
1 answer
4
iarnav asked Jan 7, 2018
1,449 views
Consider a binary tree T that has 100 leaf nodes. Then the number of INTERNAL nodes in T that have exactly two children are ______.