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
def factorial ( n ) : NEW_LINE INDENT res = 1 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT res *= i NEW_LINE DEDENT return res NEW_LINE DEDENT def binomialCoeff ( n , k ) : NEW_LINE INDENT res = 1 NEW_LINE if ( k > n - k ) : NEW_LINE INDENT k = n - k NEW_LINE DEDENT for i in range ( k ) : NEW_LINE INDENT res *= ( n - i ) NEW_LINE res //= ( i + 1 ) NEW_LINE DEDENT return res NEW_LINE DEDENT def catalan ( n ) : NEW_LINE INDENT c = binomialCoeff ( 2 * n , n ) NEW_LINE return c // ( n + 1 ) NEW_LINE DEDENT def countBST ( n ) : NEW_LINE INDENT count = catalan ( n ) NEW_LINE return count NEW_LINE DEDENT def countBT ( n ) : NEW_LINE INDENT count = catalan ( n ) NEW_LINE return count * factorial ( n ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 5 NEW_LINE count1 = countBST ( n ) NEW_LINE count2 = countBT ( n ) NEW_LINE print ( " Count ▁ of ▁ BST ▁ with " , n , " nodes ▁ is " , count1 ) NEW_LINE print ( " Count ▁ of ▁ binary ▁ trees ▁ with " , n , " nodes ▁ is " , count2 ) NEW_LINE DEDENT