#DS #Graphs

Question

Tell me
1. Possible number of BINARY TREES with n vertices ?
2. Possible number of BINARY SEARCH TREES with n vertices ?
3. Possible number of TREES with n vertices ?
4. Possible number of LABELED Trees with n vertices?
5. Possible number of UNLABELED Trees with n vertices?

Also,
 When Cayley's Formula is applied and when Catalan Number is applied ?

Answer 1

1> Total no of Binary Trees are = 

The number of binary trees can be calculated using the catalan number.

2> The number of binary search trees can be seen as a recursive solution. i.e., Number of binary search trees = (Number of Left binary search sub-trees) * (Number of Right binary search sub-trees) * (Ways to choose the root)

In a BST, only the relative ordering between the elements matter. So, without any loss on generality, we can assume the distinct elements in the tree are 1, 2, 3, 4, ...., n. Also, let the number of BST be represented by f(n) for n elements.

Now we have the multiple cases for choosing the root.

1. choose 1 as root, no element can be inserted on the left sub-tree. n-1 elements will be inserted on the right sub-tree.
2. Choose 2 as root, 1 element can be inserted on the left sub-tree. n-2 elements can be inserted on the right sub-tree.
3. Choose 3 as root, 2 element can be inserted on the left sub-tree. n-3 elements can be inserted on the right sub-tree.

...... Similarly, for i-th element as the root, i-1 elements can be on the left and n-i on the right.

These sub-trees are itself BST, thus, we can summarize the formula as:

f(n) = f(0)f(n-1) + f(1)f(n-2) + .......... + f(n-1)f(0)

Base cases, f(0) = 1, as there is exactly 1 way to make a BST with 0 nodes. f(1) = 1, as there is exactly 1 way to make a BST with 1 node.

3> In general, if there are n nodes, there exist (2n)!/(n+1)! different trees

4>No of Labelled Trees => n^n-2 

https://en.wikipedia.org/wiki/Cayley's_formula

5> The number of unlabeled binary trees is the same as the number of BSTs possible