Count BSTs with n Keys

Given an integer N, find the total number of structurally unique Binary Search Trees (BSTs) that can be made using values from 1 to N.

This problem is a direct application of the Catalan Numbers.

Examples

Example 1

• Input: n = 3
• Output: 5
• Explanation: For keys [1, 2, 3], the 5 unique BSTs are:
  1. Root = 1, Right = 2, Right-Right = 3
  2. Root = 1, Right = 3, Left-Right = 2
  3. Root = 2, Left = 1, Right = 3
  4. Root = 3, Left = 1, Right = 2
  5. Root = 3, Left = 2, Left-Left = 1

Example 2

• Input: n = 4
• Output: 14

Dynamic Programming Recurrence

To find the number of unique BSTs with n keys:

1. We choose any key i (where 1 <= i <= n) as the root.
2. The keys smaller than i (1 to i-1) must go to the left subtree. The number of unique left subtrees is count(i-1).
3. The keys larger than i (i+1 to n) must go to the right subtree. The number of unique right subtrees is count(n-i).
4. The number of BSTs with i as the root is count(i-1) * count(n-i).

Summing over all possible roots i from 1 to n gives the recurrence:

count(n) = Sum( count(i-1) * count(n-i) ) for all 1 <= i <= n

Base Cases

• count(0) = 1 (An empty tree is 1 unique BST).
• count(1) = 1 (A tree with 1 node is 1 unique BST).

Tabulation Solution (Bottom-Up DP)

We construct a 1D DP table dp of size n + 1.

function numberOfBST(n) {
    // dp[i] will store the number of unique BSTs with i keys
    const dp = new Array(n + 1).fill(0);
 
    // Base cases
    dp[0] = 1;
    dp[1] = 1;
 
    // Fill the dp table in a bottom-up manner
    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            // j represents the root element chosen
            // left subtree keys: j - 1
            // right subtree keys: i - j
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
 
    return dp[n];
}
 
// Driver code
const n = 3;
console.log(`Number of structurally Unique BSTs with ${n} keys is:`, numberOfBST(n));
// Output: Number of structurally Unique BSTs with 3 keys is: 5

Complexity Analysis

• Time Complexity: O(N^2)
  • We have a nested loop where the outer loop runs from 2 to N, and the inner loop runs up to the current outer loop value.
• Space Complexity: O(N)
  • To store the DP array of size N + 1.