Total number of possible Binary Search Trees and Binary Trees with n keys | See https : www . geeksforgeeks . org / program - nth - catalan - number / for reference of below code . ; A function to find factorial of a given number ; Calculate value of [ 1 * ( 2 ) * -- - * ( n - k + 1 ) ] / [ k * ( k - 1 ) * -- - * 1 ] ; Since C ( n , k ) = C ( n , n - k ) ; Calculate value of [ n * ( n - 1 ) * -- - * ( n - k + 1 ) ] / [ k * ( k - 1 ) * -- - * 1 ] ; A Binomial coefficient based function to find nth catalan number in O ( n ) time ; Calculate value of 2 nCn ; return 2 nCn / ( n + 1 ) ; A function to count number of BST with n nodes using catalan ; find nth catalan number ; return nth catalan number ; A function to count number of binary trees with n nodes ; find count of BST with n numbers ; return count * n ! ; Driver Program to test above functions ; find count of BST and binary trees with n nodes ; print count of BST and binary trees with n nodes
#include <bits/stdc++.h> NEW_LINE using namespace std ; unsigned long int factorial ( unsigned int n ) { unsigned long int res = 1 ; for ( int i = 1 ; i <= n ; ++ i ) { res *= i ; } return res ; } unsigned long int binomialCoeff ( unsigned int n , unsigned int k ) { unsigned long int res = 1 ; if ( k > n - k ) k = n - k ; for ( int i = 0 ; i < k ; ++ i ) { res *= ( n - i ) ; res /= ( i + 1 ) ; } return res ; } unsigned long int catalan ( unsigned int n ) { unsigned long int c = binomialCoeff ( 2 * n , n ) ; return c / ( n + 1 ) ; } unsigned long int countBST ( unsigned int n ) { unsigned long int count = catalan ( n ) ; return count ; } unsigned long int countBT ( unsigned int n ) { unsigned long int count = catalan ( n ) ; return count * factorial ( n ) ; } int main ( ) { int count1 , count2 , n = 5 ; count1 = countBST ( n ) ; count2 = countBT ( n ) ; cout << " Count ▁ of ▁ BST ▁ with ▁ " << n << " ▁ nodes ▁ is ▁ " << count1 << endl ; cout << " Count ▁ of ▁ binary ▁ trees ▁ with ▁ " << n << " ▁ nodes ▁ is ▁ " << count2 ; return 0 ; }