What's the number of distinct binary trees possible with n distinct nodes?
For a binary tree with <math>n</math> nodes, the number of edges is <math>n-1</math>. So, this problem can be reduced to the number of ways in which we can make <math>n-1</math> edges from <math>n</math> vertices. An edge can be made either as a left child of a vertex or as a right child. Hence, for <math>n</math> vertices, we have <math>2n</math> possibilities for the first edge chosen, <math>2n-1</math> for the second and so on. Thus for <math>n-1</math> edges, the total number of ways
= $2n * (2n-1) * (2n-2) * .... * (2n - (n - 2))$
= $2n * (2n-1) * (2n-2) * .... * (n + 2)$
=$ \frac{(2n)!} { (n+1)!}$
If the nodes are similar (unlabelled), then the number of distinct binary trees will be the above value divided by the number of distinct permutations possible for a binary tree structure, which will be $n!$ for a tree with n nodes.
$ \frac{(2n)!} { (n+1)! n!}$
=$\frac{2nCn}{n+1}$
Counting the number of distinct binary search trees possible for n nodes, is similar to counting the number of distinct binary trees possible for n nodes assuming nodes are unlabelled. Hence, this value will also be
=$\frac{2nCn}{n+1}$
Alternatively, for each valid binary search tree, we can get $n!$ binary trees by permuting the vertices, of which only 1 permutation is a $BST$. Hence, the total no. of binary search trees possible with $n$ nodes will be $\frac{\text{Number of distinct binary trees with $n$ nodes}} {n!}$.
What's the number of distinct binary trees possible with n distinct nodes?
For a binary tree with <math>n</math> nodes, the number of edges is <math>n-1</math>. So, this problem can be reduced to the number of ways in which we can make <math>n-1</math> edges from <math>n</math> vertices. An edge can be made either as a left child of a vertex or as a right child. Hence, for <math>n</math> vertices, we have <math>2n</math> possibilities for the first edge chosen, <math>2n-1</math> for the second and so on. Thus for <math>n-1</math> edges, the total number of ways
= $2n * (2n-1) * (2n-2) * .... * (2n - (n - 2))$
= $2n * (2n-1) * (2n-2) * .... * (n + 2)$
=$ \frac{(2n)!} { (n+1)!}$
If the nodes are similar (unlabelled), then the number of distinct binary trees will be the above value divided by the number of distinct permutations possible for a binary tree structure, which will be $n!$ for a tree with n nodes.
$ \frac{(2n)!} { (n+1)! n!}$
=$\frac{2nCn}{n+1}$
Counting the number of distinct binary search trees possible for n nodes, is similar to counting the number of distinct binary trees possible for n nodes assuming nodes are unlabelled. Hence, this value will also be
=$\frac{2nCn}{n+1}$
Alternatively, for each valid binary search tree, we can get $n!$ binary trees by permuting the vertices, of which only 1 permutation is a $BST$. Hence, the total no. of binary search trees possible with $n$ nodes will be $\frac{\text{Number of distinct binary trees with $n$ nodes}} {n!}$.
GATECSE