101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 4 main approaches to solve this problem:

  1. Recursive Approach (Brute Force) - Complex approach
  2. Memoization (Top-Down DP) - Complex approach
  3. Tabulation (Bottom-Up DP) - Complex approach
  4. Mathematical Approach (Catalan Numbers) - Complex approach

Approach 1: Recursive Approach (Brute Force)

Let's start by understanding the problem from first principles. We need to count the number of structurally unique BSTs that can be formed with n nodes.

Thinking Process: For a BST with nodes 1 to n, we can choose any number i (1 ≤ i ≤ n) as the root. Once we choose i as the root:

  • The left subtree will contain nodes 1 to i-1
  • The right subtree will contain nodes i+1 to n

The key insight is that the structure of a BST is determined by the relative order of nodes, not their absolute values. So, the number of unique BSTs with nodes 1 to i-1 is the same as the number of unique BSTs with i-1 nodes. Similarly, the number of unique BSTs with nodes i+1 to n is the same as the number of unique BSTs with n-i nodes.

Intuition: We can use recursion to solve this problem. For each possible root value i, we multiply the number of possible left subtrees by the number of possible right subtrees. Then, we sum these products for all possible root values.

Algorithm:

  1. Define a recursive function numTrees(n) that returns the number of unique BSTs with n nodes.
  2. Base case: If n = 0 or n = 1, return 1 (an empty tree or a single node tree has only one structure).
  3. For each possible root value i from 1 to n:
  4. a. Calculate the number of unique left subtrees: numTrees(i - 1)
  5. b. Calculate the number of unique right subtrees: numTrees(n - i)
  6. c. Multiply these two numbers to get the number of unique BSTs with root i.
  7. Sum up the results for all possible root values and return the total.

Time Complexity:

O(4^n / √n)

The time complexity is exponential due to the repeated calculations in the recursive approach. The exact formula is related to the Catalan number's recurrence relation.

Space Complexity:

O(n)

The space complexity is O(n) due to the recursion stack, which can go as deep as n levels.

Approach 2: Memoization (Top-Down DP)

The recursive approach works but is inefficient due to overlapping subproblems. We can optimize it using memoization.

Thinking Process: We notice that we're calculating the same values multiple times in the recursive approach. For example, numTrees(2) might be calculated multiple times for different root values.

To avoid this redundancy, we can use memoization to store the results of subproblems we've already solved. This way, when we encounter the same subproblem again, we can simply look up the result instead of recalculating it.

Intuition: Memoization transforms our exponential solution into a polynomial one by eliminating redundant calculations.

Algorithm:

  1. Create a memo array/map to store results of subproblems.
  2. Define a recursive function numTrees(n) that returns the number of unique BSTs with n nodes.
  3. Before computing, check if the result for n is already in the memo. If yes, return it.
  4. Base case: If n = 0 or n = 1, return 1.
  5. For each possible root value i from 1 to n:
  6. a. Calculate the number of unique left subtrees: numTrees(i - 1)
  7. b. Calculate the number of unique right subtrees: numTrees(n - i)
  8. c. Multiply these two numbers and add to the total.
  9. Store the result in the memo before returning.
  10. Return the total number of unique BSTs.

Time Complexity:

O(n^2)

With memoization, each value of n is computed at most once, and for each n, we iterate through n possible root values, resulting in O(n^2) time complexity.

Space Complexity:

O(n)

We use O(n) space for the memoization array and the recursion stack.

Approach 3: Tabulation (Bottom-Up DP)

We can further optimize our solution by using a bottom-up dynamic programming approach, which eliminates the need for recursion.

Thinking Process: Instead of starting from n and breaking it down into smaller subproblems (top-down), we can start from the smallest subproblems and build our way up to n (bottom-up).

Let's define dp[i] as the number of unique BSTs with i nodes. The base case is dp[0] = dp[1] = 1, representing an empty tree and a single node tree, respectively.

For dp[i], we need to consider all possible root values from 1 to i. For each root value j, the left subtree contains j-1 nodes, and the right subtree contains i-j nodes. The number of unique BSTs with root j is dp[j-1] * dp[i-j].

Intuition: By building our solution from smaller subproblems to larger ones, we can avoid recursion and its associated overhead.

Algorithm:

  1. Create a DP array of size n+1, where dp[i] represents the number of unique BSTs with i nodes.
  2. Initialize dp[0] = dp[1] = 1 (base cases).
  3. For i from 2 to n:
  4. a. For j from 1 to i (considering each possible root value):
  5. - Calculate dp[i] += dp[j-1] * dp[i-j]
  6. - Here, dp[j-1] is the number of unique left subtrees, and dp[i-j] is the number of unique right subtrees.
  7. Return dp[n] as the final answer.

Time Complexity:

O(n^2)

We have two nested loops: the outer loop runs n times, and the inner loop runs at most n times, resulting in O(n^2) time complexity.

Space Complexity:

O(n)

We use an array of size n+1 to store the DP values.

Approach 4: Mathematical Approach (Catalan Numbers)

The number of unique BSTs with n nodes is actually the nth Catalan number, which has a direct mathematical formula.

Thinking Process: The Catalan numbers are a sequence of positive integers that appear in various counting problems, often involving recursively defined objects.

The nth Catalan number can be calculated using the formula:

C(n) = (2n)! / (n! * (n+1)!)

Alternatively, it can be calculated using the formula:

C(n) = C(n-1) * (4n - 2) / (n + 1)

Intuition: By recognizing that this problem is related to Catalan numbers, we can use the mathematical formula to calculate the answer directly, without using dynamic programming.

Algorithm:

  1. Initialize result = 1.
  2. For i from 1 to n:
  3. a. Calculate result = result * (4*i - 2) / (i + 1)
  4. Return result as the final answer.

Time Complexity:

O(n)

We perform a single loop from 1 to n, with constant-time operations in each iteration.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
function numTrees(n):
    if n = 0 or n = 1:
        return 1
    
    total = 0
    for i from 1 to n:
        leftTrees = numTrees(i - 1)
        rightTrees = numTrees(n - i)
        total += leftTrees * rightTrees
    
    return total
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone