5 distinct nodes implies nodes are labelled

Dark Mode

1 vote

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.

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

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

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