5 Best Ways to Count the Number of BSTs with N Nodes in Python : Emily Rosemary Collins

Reader
March 03, 2024
5 Best Ways to Count the Number of BSTs with N Nodes in Python
by: Emily Rosemary Collins
blow post content copied from  Be on the Right Side of Change
click here to view original post

Rate this post

💡 Problem Formulation: Given a positive integer n, the task is to find the number of distinct Binary Search Trees (BSTs) that can be created using n distinct nodes. Each node contains a unique key. An example input could be n = 3, and the desired output would be 5, as there are five structurally unique BSTs that can be formed with three nodes.

Method 1: Dynamic Programming

Dynamic Programming is a method that solves problems by breaking them down into simpler subproblems. For counting BSTs, we can use the fact that the number of BSTs with n nodes is the sum of all BSTs possible by taking each node as the root. This method is often referred to as computing the nth Catalan number.

Here’s an example:

def num_trees(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]

print(num_trees(3))

Output: 5

This function num_trees initializes a list to store intermediate results and fill it in a bottom-up manner. We iterate over each count from 2 to n, and for each count, we calculate the number of unique BSTs by summing the Cartesian product of left and right subtrees counts.

Method 2: Recursive Solution

The recursive solution leverages the recursive nature of BSTs. A BST with n nodes can be recursively split into a left subtree, a root, and a right subtree. We can recursively calculate the number of unique BSTs by fixing each node as the root and combining the possibilities.

Here’s an example:

def num_trees_recursive(n):
    if n == 0 or n == 1:
        return 1
    total_trees = 0
    for i in range(1, n + 1):
        left_trees = num_trees_recursive(i - 1)
        right_trees = num_trees_recursive(n - i)
        total_trees += left_trees * right_trees
    return total_trees

print(num_trees_recursive(3))

Output: 5

The num_trees_recursive function is a straightforward recursive implementation. It calculates the number of unique BSTs for each possibility of the root node and sums them up. This method has a higher time complexity due to repeated calculations.

Method 3: Memoization

Memoization enhances the recursive method by storing the results of subproblems to avoid redundant computations. This optimization can significantly reduce the time complexity of the recursive solution for counting BSTs.

Here’s an example:

def num_trees_memoized(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n == 0 or n == 1:
        return 1
    total_trees = 0
    for i in range(1, n + 1):
        left_trees = num_trees_memoized(i - 1, memo)
        right_trees = num_trees_memoized(n - i, memo)
        total_trees += left_trees * right_trees
    memo[n] = total_trees
    return total_trees

print(num_trees_memoized(3))

Output: 5

The function num_trees_memoized accepts an integer n and a memoization dictionary. It computes the number of unique BSTs and stores the result in a memoization dictionary if it’s not already present, greatly reducing redundant calculations.

Method 4: Mathematical Formula

The number of BSTs with n nodes can also be computed directly using a mathematical formula based on Catalan numbers. This is the most efficient method as it has a linear time complexity.

Here’s an example:

from math import factorial

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

print(num_trees_math(3))

Output: 5

In the num_trees_math function, we calculate the nth Catalan number directly using a factorial-based formula that represents the exact number of unique BSTs that can be made with n nodes.

Bonus One-Liner Method 5: functools

The Python functools module can be used to apply memoization in a one-liner approach, which simplifies the implementation and still benefits from optimized performance.

Here’s an example:

from functools import lru_cache

@lru_cache(maxsize=None)
def num_trees_oneliner(n):
    if n < 2:
        return 1
    return sum(num_trees_oneliner(i) * num_trees_oneliner(n - i - 1) for i in range(n))

print(num_trees_oneliner(3))

Output: 5

By decorating the function num_trees_oneliner with @lru_cache, Python will automatically memoize the results which allows this recursive function to be written more concisely while still being efficient.

Summary/Discussion

  • Method 1: Dynamic Programming. Provides an optimal, bottom-up approach. Efficient and widely used. Rain drawback is that it requires additional space for the DP array.
  • Method 2: Recursive Solution. Simple and intuitive, but inefficient due to repeated calculations.
  • Method 3: Memoization. An optimized version of the recursive method. It is much more efficient but requires additional code for caching.
  • Method 4: Mathematical Formula. Offers a direct calculation leading to the most efficient solution. However, requires understanding of combinatorial mathematics for Catalan numbers.
  • Method 5: functools. Simplifies the recursive memoization approach through a Python module. Neat and effective but may abstract away the learning process of memoization for beginners.

March 03, 2024 at 09:47PM
Click here for more details...

=============================
The original post is available in Be on the Right Side of Change by Emily Rosemary Collins
this post has been published as it is through automation. Automation script brings all the top bloggers post under a single umbrella.
The purpose of this blog, Follow the top Salesforce bloggers and collect all blogs in a single place through automation.
============================

Salesforce