## What is the no. of distinct binary trees possible with n labeled nodes?

### Solution

For a binary tree with $n$ nodes, the no. of edges is $n-1$. So, this problem can be reduced to the no. 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 node or as a right child. Hence, for $n$ nodes, we have $2n$ possibilities for the first edge, $2n-1$ for the second edge and so on. Thus, for $n-1$ 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 is 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 is 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)

94,379 total views, 48 views today