The Gateway to Computer Science Excellence
+8 votes
474 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 by Veteran (54k points)
edited by | 474 views
0
nodes are structures and keys are value inside that structure
0
the formula cant be used for 5 nodes rt?

1 Answer

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

by Boss (35.4k points)
edited by
0

@Mk Utkarsh 

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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,209 answers
194,067 comments
95,107 users