This is a C++ Program that Solves Number of Binary Trees Problem – Catalan Numbers using Dynamic Programming technique.

How many structurally different binary trees are possible with n nodes?

In the above binary tree representations, * indicates a node of tree and / and \ indicates a left and right edge respectively.

This problem can be solved using catalan numbers. Catalan numbers forms a sequence of natural numbers based on a recursive formula(like fibonacci). Catalan numbers are used in various counting problems, this being one of them.

Let C[n]=nth catalan number

Number of structurally different binary trees with n nodes is equal to nth catalan number. So, Number of structurally different binary trees with n nodes=C[n]

Time complexity of this solution is O(n^2).

Case-1:

If n=1, result=1 *

Case-2:

If n=2, result=2 * * / \ * *

Case-3:

If n=3, result=5 * * * * * / / \ \ / \ * * * * * * / \ / \ * * * *

Here is source code of the C++ Program to Solve Number of Binary Trees Problem – Catalan Numbers. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`#include<iostream>`

using namespace std;

int catalan_binary_trees(int n)

`{`

`//we are required to find out number of structurally different binary trees with n nodes`

int c[n+1];

`//c[i]=number of structurally different binary trees with i distinct nodes`

`//we know that for 0 nodes, only one tree possible(empty tree)`

`//for a single node, there can be only 1 tree`

`//for 2 nodes, there can be just 2 tree`

`//so, we initialize the array with these values`

c[0]=1;

c[1]=1;

c[2]=2;

int i,j;

`//now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value`

for(i=3;i<=n;i++)

`{`

c[i]=0;

for(j=0;j<i;j++)

`{`

c[i]+=c[j] * c[(i-1)-j];

`}`

`}`

return c[n];

`}`

int main()

`{`

int n;

cout<<"Enter the number of distinct keys in the binary tree"<<endl;

cin>>n;

cout<<"Total number of structurally different binary trees that can be formed with "<<n<<" distinct keys are"<<endl;

cout<<catalan_binary_trees(n);

cout<<endl;

return 0;

`}`

In the main function, we ask the user to input the value for number of dinstinct keys in the binary tree. We pass this value to the function catalan_binary_trees as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Case-1: $ g++ catalan_binary_trees.cpp $ ./a.out Enter the number of distinct keys in the binary tree 5 Total number of structurally different binary trees that can be formed with 5 distinct keys are 42

**Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.**

To practice all Dynamic Programming Problems, __here is complete set of 100+ Problems and Solutions__.