hey we are going to find an exciting number called catalan number which is use to find the number of possible binary search trees from tree of a given number of nodes we will use the formula tn summationi 1 to nti1tni further details at wikipedia https en wikipedia orgwikicatalannumber our contribution basically we create the 2 function 1 catalannumbernodecount int int returns the number of possible binary search trees for n nodes 2 binarytreecountnodecount int int returns the number of possible binary trees for n nodes since here we find the binomial coefficient https en wikipedia orgwikibinomialcoefficient cn k n k nk param n 2 times of number of nodes param k number of nodes return integer value binomialcoefficient4 2 6 since cn k cn nk calculate cn k we can find catalan number many ways but here we use binomial coefficient because it does the job in on return the catalan number of n using 2ncnn1 param n number of nodes return catalan number of n nodes catalannumber5 42 catalannumber6 132 return the factorial of a number param n number to find the factorial of return factorial of n import math allfactoriali math factoriali for i in range10 true factorial5 doctest ellipsis traceback most recent call last valueerror factorial not defined for negative values return the number of possible of binary trees param n number of nodes return number of possible binary trees binarytreecount5 5040 binarytreecount6 95040 our contribution basically we create the 2 function 1 catalan_number node_count int int returns the number of possible binary search trees for n nodes 2 binary_tree_count node_count int int returns the number of possible binary trees for n nodes since here we find the binomial coefficient https en wikipedia org wiki binomial_coefficient c n k n k n k param n 2 times of number of nodes param k number of nodes return integer value binomial_coefficient 4 2 6 to kept the calculated value since c n k c n n k calculate c n k we can find catalan number many ways but here we use binomial coefficient because it does the job in o n return the catalan number of n using 2ncn n 1 param n number of nodes return catalan number of n nodes catalan_number 5 42 catalan_number 6 132 return the factorial of a number param n number to find the factorial of return factorial of n import math all factorial i math factorial i for i in range 10 true factorial 5 doctest ellipsis traceback most recent call last valueerror factorial not defined for negative values return the number of possible of binary trees param n number of nodes return number of possible binary trees binary_tree_count 5 5040 binary_tree_count 6 95040
def binomial_coefficient(n: int, k: int) -> int:
    
    result = 1  
    
    if k > (n - k):
        k = n - k
    
    for i in range(k):
        result *= n - i
        result //= i + 1
    return result


def catalan_number(node_count: int) -> int:
    
    return binomial_coefficient(2 * node_count, node_count) // (node_count + 1)


def factorial(n: int) -> int:
    
    if n < 0:
        raise ValueError("factorial() not defined for negative values")
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result


def binary_tree_count(node_count: int) -> int:
    
    return catalan_number(node_count) * factorial(node_count)


if __name__ == "__main__":
    node_count = int(input("Enter the number of nodes: ").strip() or 0)
    if node_count <= 0:
        raise ValueError("We need some nodes to work with.")
    print(
        f"Given {node_count} nodes, there are {binary_tree_count(node_count)} "
        f"binary trees and {catalan_number(node_count)} binary search trees."
    )