Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 8: | Line 8: | ||
For a binary tree with <math>n</math> nodes, the no. of edges is <math>n-1</math>. So, this problem can be reduced to the no. 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 node or as a right child. Hence, for <math>n</math> nodes, we have <math>2n</math> possibilities for the first edge, <math>2n-1</math> for the second edge and so on. Thus, for <math>n-1</math> edges, the total no. of ways | For a binary tree with <math>n</math> nodes, the no. of edges is <math>n-1</math>. So, this problem can be reduced to the no. 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 node or as a right child. Hence, for <math>n</math> nodes, we have <math>2n</math> possibilities for the first edge, <math>2n-1</math> for the second edge and so on. Thus, for <math>n-1</math> edges, the total no. of ways | ||
| − | = $2n | + | = $2n \times (2n-1) \times (2n-2)\times ....\times (2n - (n - 2))$ |
| − | = $2n * (2n-1) | + | = $2n \times* (2n-1) \times (2n-2) \times .... \times (n + 2)$ |
=$ \frac{(2n)!} { (n+1)!}$ | =$ \frac{(2n)!} { (n+1)!}$ | ||
For a binary tree with <math>n</math> nodes, the no. of edges is <math>n-1</math>. So, this problem can be reduced to the no. 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 node or as a right child. Hence, for <math>n</math> nodes, we have <math>2n</math> possibilities for the first edge, <math>2n-1</math> for the second edge and so on. Thus, for <math>n-1</math> edges, the total no. of ways
= $2n \times (2n-1) \times (2n-2)\times ....\times (2n - (n - 2))$
= $2n \times* (2n-1) \times (2n-2) \times .... \times (n + 2)$
=$ \frac{(2n)!} { (n+1)!}$
If the nodes are similar (unlabeled), then the no. of distinct binary trees will be the above value divided by the no. 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}$
(This is the $n^{th}$ Catalan number)
Counting the no. of distinct binary search trees possible for n nodes, is similar to counting the no. of distinct binary trees possible for n nodes assuming nodes are unlabeled. Hence, this value will also be
=$\frac{2nCn}{n+1}$
($n^{th}$ Catalan number)
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{No. of distinct binary trees with $n$ distinct nodes}} {n!}$
= $ \frac{(2n)!} { (n+1)! n!}$
=$\frac{2nCn}{n+1}$
($n^{th}$ Catalan number)
(We can also use the fact that for a given tree structure, there can be only 1 $BST$. Hence, no. of different $BST$s with n nodes will be equal to the no. of different binary tree structures possible for n nodes)
For a binary tree with <math>n</math> nodes, the no. of edges is <math>n-1</math>. So, this problem can be reduced to the no. 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 node or as a right child. Hence, for <math>n</math> nodes, we have <math>2n</math> possibilities for the first edge, <math>2n-1</math> for the second edge and so on. Thus, for <math>n-1</math> edges, the total no. of ways
= $2n \times (2n-1) \times (2n-2)\times ....\times (2n - (n - 2))$
= $2n \times* (2n-1) \times (2n-2) \times .... \times (n + 2)$
=$ \frac{(2n)!} { (n+1)!}$
If the nodes are similar (unlabeled), then the no. of distinct binary trees will be the above value divided by the no. 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}$
(This is the $n^{th}$ Catalan number)
Counting the no. of distinct binary search trees possible for n nodes, is similar to counting the no. of distinct binary trees possible for n nodes assuming nodes are unlabeled. Hence, this value will also be
=$\frac{2nCn}{n+1}$
($n^{th}$ Catalan number)
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{No. of distinct binary trees with $n$ distinct nodes}} {n!}$
= $ \frac{(2n)!} { (n+1)! n!}$
=$\frac{2nCn}{n+1}$
($n^{th}$ Catalan number)
(We can also use the fact that for a given tree structure, there can be only 1 $BST$. Hence, no. of different $BST$s with n nodes will be equal to the no. of different binary tree structures possible for n nodes)
GATECSE