We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Unique Binary Search Trees

Number: 96

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, TikTok, Oracle, Google, Microsoft, Clari, Bloomberg, Zoho, Snap

Problem Description

Given an integer n, return the number of structurally unique BST's (binary search trees) that can be built with n nodes, where each BST contains unique values from 1 to n.

Key Insights

  • The problem is equivalent to computing the nth Catalan number.
  • A recurrence relation can be derived: G(n) = Sum (G(i-1) * G(n-i)) for i from 1 to n.
  • Dynamic Programming is an ideal approach to avoiding redundant calculations.
  • The base case is the empty tree, which counts as 1.

Space and Time Complexity

Time Complexity: O(n^2) due to nested loops for calculating each dp state. Space Complexity: O(n) for storing the dp array.

Solution

We use Dynamic Programming where we define a dp array such that dp[i] represents the number of unique BST's possible with i nodes. Start with dp[0] = 1 (the empty tree). For each number of nodes from 1 to n, consider each node as the root, splitting the tree into a left subtree with (root-1) nodes and a right subtree with (n-root) nodes. The product of these gives the number of trees for that root, and we sum these over all possible roots. This builds the solution for dp[n] using smaller subproblems.

Code Solutions

Below are code solutions with line-by-line comments in Python, JavaScript, C++, and Java.

# Function to compute the number of unique BSTs for 'n' nodes using Dynamic Programming
def numTrees(n):
    # Initialize dp array where dp[i] stores the count of unique BSTs for i nodes
    dp = [0] * (n + 1)
    # Base case: An empty tree is considered one unique BST
    dp[0] = 1

    # Compute dp[i] for each number of nodes from 1 to n
    for nodes in range(1, n + 1):
        # Consider each possible root from 1 to nodes
        for root in range(1, nodes + 1):
            # dp[root - 1] is the number of left subtree combinations,
            # dp[nodes - root] is the number of right subtree combinations
            dp[nodes] += dp[root - 1] * dp[nodes - root]
    # Return the total count for n nodes
    return dp[n]

# Example usage:
print(numTrees(3))  # Output: 5
← Back to All Questions