Total number of possible Binary Search Trees and Binary Trees with n keys | 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 Code ; find count of BST and binary trees with n nodes ; print count of BST and binary trees with n nodes
< ? php function factorial ( $ n ) { $ res = 1 ; for ( $ i = 1 ; $ i <= $ n ; ++ $ i ) { $ res *= $ i ; } return $ res ; } function binomialCoeff ( $ n , $ k ) { $ res = 1 ; if ( $ k > $ n - $ k ) $ k = $ n - $ k ; for ( $ i = 0 ; $ i < $ k ; ++ $ i ) { $ res *= ( $ n - $ i ) ; $ res = ( int ) $ res / ( $ i + 1 ) ; } return $ res ; } function catalan ( $ n ) { $ c = binomialCoeff ( 2 * $ n , $ n ) ; return ( int ) $ c / ( $ n + 1 ) ; } function countBST ( $ n ) { $ count = catalan ( $ n ) ; return $ count ; } function countBT ( $ n ) { $ count = catalan ( $ n ) ; return $ count * factorial ( $ n ) ; } $ count1 ; $ count2 ; $ n = 5 ; $ count1 = countBST ( $ n ) ; $ count2 = countBT ( $ n ) ; echo " Count ▁ of ▁ BST ▁ with ▁ " , $ n , " ▁ nodes ▁ is ▁ " , $ count1 , " STRNEWLINE " ; echo " Count ▁ of ▁ binary ▁ trees ▁ with ▁ " , $ n , " ▁ nodes ▁ is ▁ " , $ count2 ; ? >