Problem Overview

You are given an integer n, representing the number of nodes labeled from 1 to n.
Your task is to determine how many structurally unique Binary Search Trees (BSTs) can be constructed using all the numbers from 1 to n.

In a Binary Search Tree:

• Every node’s left subtree contains values less than the node’s value.
• Every node’s right subtree contains values greater than the node’s value.

Example 1:

Input: n = 3
Output: 5

Explanation:
There are five structurally unique BSTs that can be formed using values [1, 2, 3]:

1. 1 1 2 3 3
   \ \ / \ / /
   2 3 1 3 2 1
   \ / \ /
   3 2 1 2

Example 2:

Input: n = 1
Output: 1

---

Intuition and Approach

This is a Dynamic Programming (DP) problem closely related to Catalan numbers in combinatorics.

The key idea is:
For a given n, each number i (from 1 to n) can serve as the root of a BST.

• The numbers less than i form the left subtree.
• The numbers greater than i form the right subtree.

If there are G(k) unique BSTs that can be built using k nodes, then:

• The number of unique BSTs with i as the root is G(i - 1) * G(n - i)
  (because the left and right subtrees can combine independently).

Hence,

G(n) = Σ (G(i - 1) * G(n - i))   for i = 1 to n

with base cases:

G(0) = 1
G(1) = 1

---

Step-by-Step Explanation

1. Base Case
   • G(0) = 1 (empty tree is one unique structure)
   • G(1) = 1 (a single node is one unique BST)
2. Recursive Relation
   For each n, choose a number i as root:
   • Left subtree has (i - 1) nodes
   • Right subtree has (n - i) nodes
   • Total combinations = G(i - 1) * G(n - i)
3. Dynamic Programming Implementation
   • We build G(n) bottom-up using a DP array.
   • Each G(n) depends on all smaller values of G.

---

Java Code Implementation

public class UniqueBinarySearchTrees {

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        
        // Base cases
        dp[0] = 1;
        dp[1] = 1;
        
        // Fill dp array for all values up to n
        for (int nodes = 2; nodes <= n; nodes++) {
            for (int root = 1; root <= nodes; root++) {
                dp[nodes] += dp[root - 1] * dp[nodes - root];
            }
        }
        
        return dp[n];
    }
}

---

Example Walkthrough

Let’s take n = 3

We know:

G(0) = 1  
G(1) = 1  

Now compute:

n	Formula	Calculation	Result
2	G(1)*G(0) + G(0)*G(1)	11 + 11	2
3	G(2)*G(0) + G(1)*G(1) + G(0)*G(2)	21 + 11 + 1*2	5

Hence, G(3) = 5.

---

Complexity Analysis

• Time Complexity: O(n²)
  For each n, we iterate through all possible roots.
• Space Complexity: O(n)
  We use a one-dimensional DP array of size n + 1.

---

Mathematical Insight (Catalan Numbers)

The sequence of unique BST counts follows the Catalan number pattern:

Cₙ = (1 / (n + 1)) * (2n choose n)

So,

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

For small n, the DP approach is simpler and avoids integer overflow.
For large n, using the Catalan number formula with BigInteger in Java is more efficient.

---

Alternative Approach (Using Catalan Formula)

import java.math.BigInteger;

public class UniqueBinarySearchTreesFormula {

    public int numTrees(int n) {
        BigInteger numerator = BigInteger.ONE;
        BigInteger denominator = BigInteger.ONE;
        
        for (int i = 0; i < n; i++) {
            numerator = numerator.multiply(BigInteger.valueOf(2L * n - i));
            denominator = denominator.multiply(BigInteger.valueOf(i + 1));
        }
        
        BigInteger catalan = numerator.divide(denominator);
        catalan = catalan.divide(BigInteger.valueOf(n + 1));
        
        return catalan.intValue();
    }
}