Calculating the Number of Possible BSTs with n Distinct Nodes in Python

March 2, 2024 by Emily Rosemary Collins

💡 Problem Formulation: When working with Binary Search Trees (BSTs), one may wonder how many structurally distinct BSTs can be created using ‘n’ distinct nodes. Each tree must uphold the property that left descendants are less than the node and right descendants are greater. Given an integer ‘n’, the goal is to compute the total number of unique BSTs possible. For instance, inputting ‘n = 3’ would produce an output of ‘5’, as there are five unique BSTs that can be constructed with three distinct nodes.

Method 1: Dynamic Programming

This method involves using dynamic programming to count the number of possible BSTs. The approach is based on the idea that the number of trees with ‘n’ nodes is the sum of all trees possible with ‘i-1’ nodes as left children and ‘n-i’ nodes as right children for each ‘i’ between 1 and ‘n’. The function will follow this specification and make use of memoization to store intermediate results and avoid redundant calculations.

Here’s an example:

def num_trees(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return 1
    total = 0
    for i in range(1, n+1):
        total += num_trees(i-1, memo) * num_trees(n-i, memo)
    memo[n] = total
    return total

# Example usage:
print(num_trees(3))

The output of this code snippet would be:

This function, num_trees(), demonstrates an application of dynamic programming to solve the problem. It uses a dictionary, memo, to store the number of BSTs that can be formed with a given number of nodes to avoid recalculating results. The recursive nature of the function allows it to break down the original problem into smaller subproblems, which can be combined to obtain the final result.

Method 2: Mathematical Deduction

The mathematical approach involves calculating the number of possible BSTs using the Catalan number formula. Catalan numbers have a direct correlation with the number of BSTs because they enumerate various combinatorial structures, BSTs being one of them. The nth Catalan number is given by the formula C(n) = (2n)! / ((n+1)!n!). This method will create a function that calculates the nth Catalan number to determine the number of BSTs.

Here’s an example:

from math import factorial

def catalan_number(n):
    return factorial(2*n) // (factorial(n+1) * factorial(n))

# Example usage:
print(catalan_number(3))

The output of this code snippet would be:

The function catalan_number() computes the nth Catalan number, which represents the number of possible BSTs that can be generated using ‘n’ distinct nodes. It utilizes Python’s builtin factorial function from the math module to carry out the calculations described by the Catalan number formula.

Method 3: Iterative Computation

Similar to the dynamic programming approach, this method iteratively computes the number of BSTs for each number from 1 to ‘n’ using previous results. It sets up an array to track the number of trees possible with ‘i’ nodes and iteratively fills it in a bottom-up manner. This process reduces the number of recursive calls that would otherwise be necessary in a purely recursive solution.

Here’s an example:

def num_trees_iterative(n):
    G = [0] * (n + 1)
    G[0], G[1] = 1, 1

    for i in range(2, n + 1):
        for j in range(1, i + 1):
            G[i] += G[j - 1] * G[i - j]

    return G[n]

# Example usage:
print(num_trees_iterative(3))

The output of this code snippet would be:

The num_trees_iterative() function builds the number of trees from smaller to larger numbers of nodes. This iterative approach is more space efficient than a simple recursive method because it avoids the overhead of recursive calls and only requires storage for an array of size ‘n+1’.

Method 4: Avoiding Factorial with a Simpler Formula

Instead of using the heavy factorial-based Catalan formula, it is possible to use a binomial coefficient-based formula for Catalan numbers, which is C(n) = C(2n, n) / (n + 1). The function will implement this optimized formula to compute the number of BSTs without dealing with large factorials that can cause overflow issues for large ‘n’.

Here’s an example:

def binomial_coefficient(n, k):
    if k > n - k:
        k = n - k
    res = 1
    for i in range(k):
        res *= (n - i)
        res //= (i + 1)
    return res

def catalan(n):
    c = binomial_coefficient(2 * n, n)
    return c // (n + 1)

# Example usage:
print(catalan(3))

The output of this code snippet would be:

The function binomial_coefficient() computes the binomial coefficient in an efficient manner, avoiding the factorial operations. The function catalan() uses this to calculate the Catalan number which corresponds to the number of BSTs possible with ‘n’ distinct nodes.

Bonus One-Liner Method 5: List Comprehension with memoization

This unique one-liner approach uses list comprehension and memoization to calculate the nth Catalan number. By utilizing Python’s ability to compute values and store them in a list with just one line of code, this method provides a concise alternative to the iterative and recursive solutions.

Here’s an example:

def catalan_n(n, memo=[1, 1] + [0] * (n-1)):
    return memo[n] or sum(memo[i] * memo[n-1-i] for i in range(n))

# Example usage:
print(catalan_n(3))

The output of this code snippet would be:

The function catalan_n() makes use of Python’s list comprehension and short-circuit evaluation to elegantly compute the nth Catalan number, which determines the number of BSTs that can be generated. It is capable of efficiently handling repeated computations by using a memoization technique embedded within the list itself.

Summary/Discussion

Method 1:

Method 2:

Method 3:

Method 4:

Method 5: