number of possible binary trees Algorithm

The number of possible binary trees algorithm is a fundamental concept in computer science and combinatorics, which deals with counting the distinct binary trees that can be formed using a given number of nodes. A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. The algorithm helps in understanding the different ways to arrange a certain number of nodes in the tree, which is useful in various applications such as compiler optimizations, searching and sorting algorithms, and dynamic programming. The most common technique to calculate the number of possible binary trees is using the concept of Catalan numbers. Catalan numbers are a sequence of natural numbers that have many applications in combinatorial mathematics, including counting the number of binary trees for a given number of nodes. The nth Catalan number can be calculated using the formula C(n) = (2n)! / ((n+1)!n!) for n ≥ 0. In the context of binary trees, the number of possible binary trees with 'n' nodes is given by the nth Catalan number. The algorithm can be further optimized using dynamic programming or memoization to store the results of previously calculated Catalan numbers, reducing the time complexity and making it more efficient for larger inputs. 
"""
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: t(n) = SUMMATION(i = 1 to n)t(i-1)t(n-i)
 
Further details at Wikipedia: https://en.wikipedia.org/wiki/Catalan_number
"""
"""
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.
"""
 
 
def binomial_coefficient(n: int, k: int) -> int:
    """
    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
    """
    result = 1  # To kept the Calculated Value
    # Since C(n, k) = C(n, n-k)
    if k > (n - k):
        k = n - k
    # Calculate C(n,k)
    for i in range(k):
        result *= n - i
        result //= i + 1
    return result
 
 
def catalan_number(node_count: int) -> int:
    """
    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 binomial_coefficient(2 * node_count, node_count) // (node_count + 1)
 
 
def factorial(n: int) -> int:
    """
    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
    """
    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 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
    """
    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."
    )

LANGUAGE:

DARK MODE:

PROGRAMMING LANGUAGES:

Python

Java

Javascript

C#

C++

C

Ruby

Scala

MATLAB

Kotlin

Rust

R

Go