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


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           *


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


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.

  1. #include<iostream>
  2. using namespace std;
  4. int catalan_binary_trees(int n)
  5. {
  6.     //we are required to find out number of structurally different binary trees with n nodes
  7.     int c[n+1];
  9.     //c[i]=number of structurally different binary trees with i distinct nodes
  11.     //we know that for 0 nodes, only one tree possible(empty tree)
  12.     //for a single node, there can be only 1 tree
  13.     //for 2 nodes, there can be just 2 tree
  14.     //so, we initialize the array with these values
  15.     c[0]=1;
  16.     c[1]=1;
  17.     c[2]=2;
  19.     int i,j;
  21.     //now, using bottom up DP, we will implement the recursive formula of catalan number to find the required value
  22.     for(i=3;i<=n;i++)
  23.     {
  24.         c[i]=0;
  26.         for(j=0;j<i;j++)
  27.         {
  28.             c[i]+=c[j] * c[(i-1)-j];
  29.         }
  30.     }
  32.     return c[n];
  33. }
  35. int main()
  36. {
  37.     int n;
  39.     cout<<"Enter the number of distinct keys in the binary tree"<<endl;
  40.     cin>>n;
  42.     cout<<"Total number of structurally different binary trees that can be formed with "<<n<<" distinct keys are"<<endl;
  43.     cout<<catalan_binary_trees(n);
  45.     cout<<endl;
  46.     return 0;
  47. }
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
$ g++ catalan_binary_trees.cpp
$ ./a.out
Enter the number of distinct keys in the binary tree
Total number of structurally different binary trees that can be formed with 5 distinct keys are

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.