Binary Trees with N Keys Problem - Dynamic Programming Solutions

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

Problem Description

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

Problem Solution

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]

Note: Join free Sanfoundry classes at Telegram or Youtube

Recurrence relation –

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

Expected Input and Output

Case-1:

Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

 
If n=1, result=1           *

Case-2:

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

Case-3:

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

Program/Source Code

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;
```
```
}
```

Program Explanation

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.

Runtime Test Cases

 
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.

« Prev - Fibonacci Series using Dynamic Programming

» Next - Parentheses Expressions Problem – Catalan Numbers

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Buy Data Structure Books
Buy Computer Science Books
Apply for Information Technology Internship
Practice Computer Science MCQs
Buy Programming Books

Recommended Articles: