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).
If n=1, result=1 *
If n=2, result=2 * * / \ * *
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.
using namespace std;
int catalan_binary_trees(int n)
//we are required to find out number of structurally different binary trees with n nodes
//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
//now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value
c[i]+=c[j] * c[(i-1)-j];
cout<<"Enter the number of distinct keys in the binary tree"<<endl;
cout<<"Total number of structurally different binary trees that can be formed with "<<n<<" distinct keys are"<<endl;
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.