Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 5: | Line 5: | ||
For a binary tree with n nodes, the number of edges is n-1.So, this problem can be reduced to the number of ways in which we can make n-1 edges from n vertices. An edge can be made either as a left child of a vertex or as a right child. Hence, for n vertices, we have 2n possibilities for the first edge chosen, 2n-1 for the second and so on. Thus for n-1 the total number of ways | For a binary tree with n nodes, the number of edges is n-1.So, this problem can be reduced to the number of ways in which we can make n-1 edges from n vertices. An edge can be made either as a left child of a vertex or as a right child. Hence, for n vertices, we have 2n possibilities for the first edge chosen, 2n-1 for the second and so on. Thus for n-1 the total number of ways | ||
| − | = 2n * (2n-1) * (2n-2) * .... * (2n - (n - 2)) | + | = $2n * (2n-1) * (2n-2) * .... * (2n - (n - 2))$ |
| − | = 2n * (2n-1) * (2n-2) * .... * (n + 2) | + | |
| + | = $2n * (2n-1) * (2n-2) * .... * (n + 2)$ | ||
| + | |||
=$ \frac{(2n)!} { (n+1)!}$ | =$ \frac{(2n)!} { (n+1)!}$ | ||
What's the number of distinct binary trees possible with n distinct nodes?
For a binary tree with n nodes, the number of edges is n-1.So, this problem can be reduced to the number of ways in which we can make n-1 edges from n vertices. An edge can be made either as a left child of a vertex or as a right child. Hence, for n vertices, we have 2n possibilities for the first edge chosen, 2n-1 for the second and so on. Thus for n-1 the total number of ways
= $2n * (2n-1) * (2n-2) * .... * (2n - (n - 2))$
= $2n * (2n-1) * (2n-2) * .... * (n + 2)$
=$ \frac{(2n)!} { (n+1)!}$
What's the number of distinct binary trees possible with n distinct nodes?
For a binary tree with n nodes, the number of edges is n-1.So, this problem can be reduced to the number of ways in which we can make n-1 edges from n vertices. An edge can be made either as a left child of a vertex or as a right child. Hence, for n vertices, we have 2n possibilities for the first edge chosen, 2n-1 for the second and so on. Thus for n-1 the total number of ways
= $2n * (2n-1) * (2n-2) * .... * (2n - (n - 2))$
= $2n * (2n-1) * (2n-2) * .... * (n + 2)$
=$ \frac{(2n)!} { (n+1)!}$
GATECSE