The Gateway to Computer Science Excellence

+9 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?

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?

+6 votes

Best answer

**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!}$

0

In case of binary tree distinct key and labeled node both give the same answer ??

and

In case of the Binary search tree, distinct key and unlabeled node give the same answer??

+1

For labelled nodes number of BT will be less then (nth Catalan number * n! ), if the keys aren't distinct.

+1

the main reason for labeling a node is to make it distinct

so there is no point of labeling 2 nodes with same label

so there is no point of labeling 2 nodes with same label

+1

Agreed!!! Made that comment to clarify so that no one is confused regarding the non-distinct key case.

0

@smsubham @Mk Utkarsh In case of no of BT with labelled nodes(Q6), if there is one key which is repeated thrice then no of BT would be =(nth Catalan number * n!)/3!

Is this fine?

What if I modify Q4 as "How many binary trees possible with **11 keys with one key repeated thrice**?"

Would that be same as (nth Catalan number * n!)/3!?

Please differentiate Q4 & Q6 with above modification.

52,375 questions

60,615 answers

202,052 comments

95,433 users