A binary tree is full if all of its vertices have either zero or two children. Let ${\mathit{B}}_{\mathbf{n}}$denote the number of full binary trees with n vertices. (a)By drawing out all full binary trees with 3, 5, or 7 vertices, determine the exact values of ${\mathit{B}}_{\mathbf{3}}$, ${\mathit{B}}_{\mathbf{5}}$, and ${\mathit{B}}_{\mathbf{7}}$. Why have we left out even numbers of vertices, like ${\mathit{B}}_{\mathbf{4}}$?

(b) For general n, derive a recurrence relation for ${\mathit{B}}_{\mathbf{n}}$.

(c) Show by induction that ${\mathit{B}}_{\mathbf{n}}$is $\mathit{\Omega }\left(2^n\right)$.

All binary trees having 3, 5, and 7 nodes are shown in following diagrams:

The following is a binary tree with three vertices$B_3$:

From either the multiple endpoints, only one full binary tree can be drawn.

As a result, the precise value of$B_3$is 1.

$B_3=1$

The binary tree with five vertices$B_5$is shown below:

Here, two binary trees can be drawn from the five vertices. Therefore, the exact value of$B_5$is 2 .

The binary tree with five vertices$B_7$is shown below:

From of the seven edges, five binary trees may be drawn. As a result, the precise value of$B_7$is 5.

The number of edges in a complete binary tree must be odd.

As a result, there is no requirement for$B_4$or ${\mathrm{B}}_6$etc.

Recurrence relation for ${\mathbf{B}}_{\mathbf{n}}$is given below:

The number of entire binary trees is equal to the total of the products of something like the series of binary trees from the child trees.

${\mathrm{B}}_{\mathrm{n}}=\sum _{\mathrm{i}=1}^{\mathrm{n}-2}{\mathrm{B}}_{\mathrm{i}}{\mathrm{B}}_{\mathrm{n}-\mathrm{i}-1}$

That number of sensor nodes inside the left sub-tree is I while the number of nodes in the right sub-tree is n-i-1.

When n=5 is the number of vertices in a binary tree, the precise value of $B_5$is given as follows:

$$\begin{gathered} {\mathrm{B}}_5=\sum _{\mathrm{i}=1}^{5-2}{\mathrm{B}}_{\mathrm{i}}{\mathrm{B}}_{5-\mathrm{i}-1} \\ ={\mathrm{B}}_1{\mathrm{B}}_3+{\mathrm{B}}_2{\mathrm{B}}_2+{\mathrm{B}}_3{\mathrm{B}}_1 \\ =1+0+1 \\ =2 \end{gathered}$$

As a result, there are two binary trees produced for every five vertices.

As a result, the recurrence relation is shown to be valid ${\mathrm{B}}_n=\sum _{\mathrm{i}=1}^{n-2}{\mathrm{B}}_{\mathrm{i}}{\mathrm{B}}_{n-\mathrm{i}-1}$

The proof is as follows:

Display that,$B_n\ge 2\left(\frac{n-3}{2}\right)$

Base case:

$$\begin{gathered} \mathrm{n}=1 \\ {\mathrm{B}}_1=1\ge 2^{-1} \\ {\mathrm{B}}_3=1\ge 2° \end{gathered}$$

Inductive steps:

For $n\ge 3$odd:

$$\begin{gathered} B_{n+2}=\sum _{i=1}^{n+1}{B}_i{B}_{n-i-1}\ge \frac{n+2}{2}\times 2^{\frac{n-5}{2}}\ge 2^{2\frac{n-5}{2}} \\ =2^{\frac{n-1}{2}} \end{gathered}$$

Thus, it is proved that ${\mathrm{B}}_{\mathrm{n}}$ would be $\Omega {(\mathrm{n}}^2)$.