513 views
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?
in DS
edited | 513 views
0
0
nodes are structures and keys are value inside that structure
0
the formula cant be used for 5 nodes rt?

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

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

by Boss (36.7k points)
edited
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
yes but there is no such thing as unlabeled BST
+1
Ok I understand
+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
+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.

+1

Mamta Satywali edited.