in DS
444 views
1 vote
1 vote
With 5 distinct nodes, the maximum no. of binary trees that can be formed is _____
in DS
by
444 views

2 Comments

5 distinct nodes implies nodes are labelled
0
0
Catalan number returns the total count of structurally independent binary trees.

For each structurally independent binary tree, there can only be one BST, and only one unlabelled binary tree made out of it.

To get labelled binary tree, we can permute the labels in the nodes of a structure in n! ways.
0
0

2 Answers

2 votes
2 votes
Best answer
Catalan Number gives the count of distinct binary trees with nodes that cannot be distinguished with each other,i.e unlabelled nodes and only the structure of tree is different.

But, here nodes are distinct A,B,C,D,E and total permutations of them = 5! = 120 .

So, each structure of tree includes these permutations.

Hence, maximum number of BT = Catalan number * 120 = 5040
selected by
by

3 Comments

If question said $5$ nodes instead of 5 distinct nodes, then answer would be 42. rt??

0
0
yes i.e. binary search tree.
0
0
i think the answer should be 42..

please suggest
0
0
0 votes
0 votes
We have to maximise the number of binary trees, so go with labelled.

So, 5th Catalan multiplied by 5 factorial.

$\frac{10*9*8*7*6}{6*5*4*3*2}*5!=5040$
Answer:

Related questions