Given a number of nodes, count how many BSTs we can construct

count_bst.py

def countBST(n):
    """
    :param n: a positive integer
    :return: Number of all possible binary search trees (BST) with n unique numbers
    The number is called a Catalan number F(n) = C(2*n, n) / (n+1) = (2*n)! / (n+1)! * n!
    As the above formula involves calculating factorial which is laborious and can overflow in some cases,
    We can use the following recurrence relation to make the calculation simple.
    F(0) = 1
    F(n+1) = (2*(2*n + 1) / (n+2)) * F(n)
    """
    result = 1
    for i in range(1, n):
        result = 2 * (2 * i + 1) * result // (i + 2)
    return result


def main():
    n = int(input("How many nodes? "))
    print("Number of BSTs: {}".format(countBST(n)))


if __name__ == '__main__':
    main()