Lecture 263:- Number of Binary Trees using N Nodes

The number of binary trees that can be formed using N nodes can be calculated using the concept of Catalan numbers. The Catalan numbers are a sequence of natural numbers that have many applications in combinatorial mathematics, including counting the number of different binary trees with a given number of nodes.

The formula to calculate the number of binary trees with N nodes is:

C(N) = (2N)! / [(N + 1)! * N!]

where C(N) is the Nth Catalan number.

Here's a C++ function to calculate the number of binary trees using N nodes:

cppCopy code

#include <iostream> unsigned long long int factorial(int n) {    unsigned long long int result = 1;    for (int i = 1; i <= n; ++i) {        result *= i;    }    return result; } unsigned long long int catalanNumber(int N) {    return factorial(2 * N) / (factorial(N + 1) * factorial(N)); } int main() {    int N;    std::cout << "Enter the number of nodes (N): ";    std::cin >> N;    unsigned long long int numBinaryTrees = catalanNumber(N);    std::cout << "Number of binary trees with " << N << " nodes: " << numBinaryTrees << std::endl;    return 0; }

In this program, we calculate the factorial of a number using the factorial() function. The catalanNumber() function uses the formula to calculate the Nth Catalan number, which gives us the number of binary trees with N nodes.

Note that the Catalan numbers can grow very rapidly, and for large values of N, the result may become too large to be stored in a standard data type. In such cases, you may need to use a library that supports big integers or modify the algorithm to handle large numbers efficiently.