Difference between revisions of "Number of Binary trees possible with n nodes"

(→‎Solution)
 
(41 intermediate revisions by one other user not shown)
Line 1: Line 1:
−
<metadesc>What's the number of distinct binary trees possible with n distinct nodes? </metadesc>
+
<metadesc>What's the number of distinct binary trees possible with n labeled nodes?
−
<metadesc>What's the number of distinct binary trees possible with n unlabelled nodes? </metadesc>
+
What's the number of distinct binary trees possible with n unlabeled nodes?  
−
<metadesc>What's the number of distinct binary search trees possible with n nodes? </metadesc>
+
What's the number of distinct binary trees structures possible with n nodes?  
−
What's the number of distinct binary trees possible with n distinct nodes?
+
What's the number of distinct binary search trees possible with n nodes? </metadesc>
 +
==What's the no. of distinct binary trees possible with n labeled nodes?==
  
 
===Solution===
 
===Solution===
−
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  
+
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-1) * (2n-2) * .... * (2n - (n - 2))$
+
= $2n \times (2n-1) \times (2n-2)\times ....\times (2n - (n - 2))$
  
−
= $2n * (2n-1) * (2n-2) * .... * (n + 2)$
+
= $2n \times (2n-1) \times (2n-2) \times .... \times (n + 2)$
  
 
=$ \frac{(2n)!} { (n+1)!}$
 
=$ \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.
+
==What's the no. of distinct binary trees possible with n unlabeled nodes? (No. of structurally different binary trees possible with n nodes)==
 +
 
 +
===Solution===
 +
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{(2n)!} { (n+1)!  n!}$
 +
 +
=$\frac{2nCn}{n+1}$
 +
 +
(This is the $n^{th}$ [http://en.wikipedia.org/wiki/Catalan_number Catalan number])
 +
 +
==What's the no. of distinct binary search trees possible with n nodes?==
 +
===Solution===
 +
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}$  
 
=$\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
+
($n^{th}$ [http://en.wikipedia.org/wiki/Catalan_number Catalan number])
  
−
=$\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 [http://en.wikipedia.org/wiki/Binary_search_tree $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!}$
  
−
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!}$
 
 
= $ \frac{(2n)!} { (n+1)!  n!}$
 
= $ \frac{(2n)!} { (n+1)!  n!}$
  
 
=$\frac{2nCn}{n+1}$  
 
=$\frac{2nCn}{n+1}$  
 +
 +
($n^{th}$ [http://en.wikipedia.org/wiki/Catalan_number Catalan number])
 +
 +
(We can also use the fact that for a given tree structure, there can be only 1 [http://en.wikipedia.org/wiki/Binary_search_tree $BST$]. Hence, no. of different [http://en.wikipedia.org/wiki/Binary_search_tree $BST$]s with n nodes will be equal to the no. of different binary tree structures possible for n nodes)
 +
  
 
{{Template:FBD}}
 
{{Template:FBD}}
  
−
[[Category: Probability and Combinatorics ]]
+
[[Category: Combinatory Notes]]
 +
 
 +
 
 +
[[Category: Compact Notes for Reference of Understanding]]

Latest revision as of 01:01, 7 May 2015

What's the no. of distinct binary trees possible with n labeled nodes?

Solution

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)!}$

What's the no. of distinct binary trees possible with n unlabeled nodes? (No. of structurally different binary trees possible with n nodes)

Solution

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)

What's the no. of distinct binary search trees possible with n nodes?

Solution

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)




blog comments powered by Disqus
Retrieved from "https://gatecse.in/w/index.php?title=Number_of_Binary_trees_possible_with_n_nodes&oldid=5094"


What's the number of distinct binary trees possible with n distinct nodes?

Solution[edit]

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!}$ = $ \frac{(2n)!} { (n+1)! n!}$

=$\frac{2nCn}{n+1}$




blog comments powered by Disqus