Q:

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

belongs to collection: C++ programs on various topics

mahmoud2506
Save to bookmark
|
2022-05-05
|
  223 
0

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

C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-05
need an explanation for this answer? contact us directly to get an explanation for this answer

If we consider root as the ith node then:

  1. i-1 nodes are there in left subtree.
  2. 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 :

catalan-number

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

Recurrence relation:

catalan-number

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

C++ programs on various topics
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
C++ program to find first occurrence of a Number U... >>
<< C++ program to print all subsequences of a String...