# C++ program to find number of BSTs with N nodes (Catalan numbers)

Here, we are implementing a **C++ program to find number of BSTs with N Nodes (Catalan numbers)**.

Submitted by Saksham Bhayana, on December 09, 2018

**Problem statement:** C++ program to find number of binary search trees with n nodes.

**Input format:** single integer *n*

**Constraints:** 0=<n<=15

**Sample input:** 4

**Sample output:** 14 binary search tree/trees are there for 4 nodes

**Problem explanation:**

The **number of BSTs with n vertices** is given by Catalan numbers. For n=0,1,2,3,4... Catalan numbers are 1,1,2,5,14... and so on.

Catalan numbers are given by **Cn = (2n)!/(n+1)!*n! = count of BSTs with nodes n**.

Catalan numbers are used here to find the count of BSTs because both satisfy same recurrence relation that is:

For **n=0** number of trees is **1** i.e. empty tree. For subsequent values:

And, so on...

**Solution:**

If we consider root as the **i ^{th}** node then:

**i-1**nodes are there in left subtree.**n-i**nodes are there in right subtree.

Let’s denote count of BST by Bn for n elements

The 2 subtrees here will be independent of each other. Therefore it will be ( B i-1 * B n-i ) for Bi . For n nodes (as i has n choices) it will be :

Since the recurrence relation is same as of catalan numbers , so count of BST is given by Cn.

**Recurrence relation:**

This gives complexity O(4^n). Complexity can be reduced to O(n^2) by using DP.

**C++ implementation:**

#include <iostream> using namespace std; int CN(int n){ int Cn =0; // base case if(n==0) // empty tree { return 1; } for(int i=1;i<n+1;i++) { Cn+= CN(i-1)*CN(n-i); } return Cn; } int main(){ int n; cout<<"Enter number of nodes: "; cin>>n; cout<<n<<endl; int trees=CN(n); cout<<trees<<" binary search trees are there for "<<n<<" nodes"<<endl; return 0; }

**Output**

Enter number of nodes: 4 14 binary search trees are there for 4 nodes

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.