GATE Overflow | Data Structures | Test 1 | Question: 10

Question

With 5 distinct nodes, the maximum no. of binary trees that can be formed is _____

Comments

5 distinct nodes implies nodes are labelled

---

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.

Answer 1

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

Comments

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

---

yes i.e. binary search tree.

---

i think the answer should be 42..

please suggest

Answer 2

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$