This article explains the correct dynamic programming solution for LeetCode 96: Unique Binary Search Trees.
I also document a common mistake that many learners make, including myself: trying to derive dp[n] by inserting a new node into all BSTs of size n-1. This approach looks intuitive but is mathematically incorrect.

In this post, I explain:

1. What dp[n] really means

2. Why the “insert a new node into dp[n-1]” idea fails

3. The correct recurrence relation

4. The Catalan number connection

5. The final Java solution

---

Problem Summary

Given an integer n, return the number of structurally unique binary search trees (BSTs) containing values from 1 to n.

Example:

• Input: 3
  Output: 5

• Input: 1
  Output: 1

Constraints: 1 <= n <= 19.

---

1. Correct Definition of DP

We define:

dp[i] = the number of structurally unique BSTs that can be built using i distinct nodes (values from 1 to i).

Base cases:

• dp[0] = 1 (an empty tree is considered one valid structure)

• dp[1] = 1

---

2. The Incorrect Thought Process (and Why It Fails)

My initial idea looked like this:

dp[n] comes from dp[n-1] by inserting the new node n.
So maybe dp[n] = 2 * dp[n-1] + 1 ?

The reasoning behind this idea:

• If we take all BSTs of size n-1, we can insert the new value n somewhere.

• Maybe we can insert it as the rightmost leaf or somewhere else.

• For small values like n = 2 or n = 3, this formula accidentally matches the answer.

This is misleading.

Why this approach is wrong

1. BST structure is determined by the root, not by incremental insertion.
   You cannot obtain all unique BSTs by simply inserting a new node into every existing tree.

2. Insertion order does not map to unique tree shapes.
   Many insertion sequences produce the same final BST.
   Conversely, some tree shapes cannot be produced by any single sequence of “append one node”.

3. It fails immediately at n = 4.
   The correct answer is 14, but
   2*dp[3] + 1 = 2*5 + 1 = 11
   which is wrong.

4. The formula ignores root choice.
   Every number from 1 to n can be the root of the BST.
   This global structural choice cannot be captured by “insert a node at the end”.

This mistake is extremely common. It happens because we confuse “insertion process” with “counting possible structures”.

---

3. The Correct DP Formula: Root Enumeration

To build a BST with i nodes, choose a root j (1 ≤ j ≤ i):

• The left subtree has j - 1 nodes.

• The right subtree has i - j nodes.

The total number of trees for root j is:

dp[j-1] * dp[i-j]

Because BST shapes combine independently:
(left subtree shape) × (right subtree shape).

So the full recurrence is:

dp[i] = Σ ( dp[j-1] * dp[i-j] ) for j = 1 to i

This is the classic recurrence of the Catalan numbers.

---

4. Catalan Numbers and BST Counting

LeetCode 96 is a direct application of Catalan numbers.

The nth Catalan number is given by:

C₀ = 1
C₁ = 1
C₂ = 2
C₃ = 5
C₄ = 14
...

This matches exactly the number of unique BSTs for n nodes.

The DP recurrence we computed is the DP version of this sequence.

---

5. Java Implementation (Dynamic Programming)

class Solution {
    public int numTrees(int n) {
        if (n == 0) {
            return 1;
        }

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}

---

6. Key Takeaways

1. The number of unique BSTs does not come from inserting one new node into dp[n-1].

2. The correct solution requires enumerating each possible root.

3. The left and right subtree sizes determine the total number of combinations.

4. The solution matches the Catalan number sequence.

5. Dynamic programming is a natural and efficient way to compute results up to n = 19.

7. Common Mistakes When Solving “Unique Binary Search Trees”

1. Trying to derive dp[n] from dp[n-1]

Many beginners assume:

“Take all BSTs with n–1 nodes, insert node n somewhere, and get dp[n].”

This is incorrect because:

• BST structure is determined by the choice of root, not insertion order.

• Inserting the largest number n only explores a limited subset of possible tree shapes.

• Many valid BST shapes cannot be formed by simply adding the largest value to an existing tree.

This leads to incorrect formulas such as:

dp[n] = 2 * dp[n-1] + 1

This accidentally matches dp[3] = 5 but fails immediately at n = 4
(correct value is 14, not 11).

---

2. Forgetting dp[0] = 1

dp[0] = 1 represents an empty tree.

It is essential because:

• When choosing a root, sometimes the left subtree has zero nodes.

• If dp[0] = 0, all structures with empty subtrees would collapse to zero.

---

3. Ignoring root enumeration

Some learners try to build dp by only looking at tree sizes, but the key is:

Every number j (1 to n) can serve as the root.

For root j:

• Left subtree has j–1 nodes → dp[j–1] ways

• Right subtree has n–j nodes → dp[n–j] ways

• Total for this root: dp[j–1] * dp[n–j]

Forgetting this leads to incomplete counting.

---

4. Misinterpreting BST structure as “permutation trees”

Some students think each permutation of [1…n] builds a unique BST.

Wrong.

Different insertion sequences can create the same BST shape.

The number of unique BSTs is far smaller than n!
and is exactly the Catalan number Cₙ.

---

Visual Diagram: How Root Enumeration Works

Here is a simple ASCII diagram showing how dp[3] = 5 is derived.

Step 1 — n = 3

Possible roots: 1, 2, 3

Values: 1, 2, 3

---

Case 1: Root = 1

Left subtree: 0 nodes → dp[0]
Right subtree: 2 nodes → dp[2]

   1
    \
     2
      \
       3

or

   1
    \
     3
    /
   2

Total contributed by root=1
\= dp[0] dp[2]
\= 1 2 = 2

---

Case 2: Root = 2

Left subtree: 1 node → dp[1]
Right subtree: 1 node → dp[1]

Only one structure:

    2
   / \
  1   3

Total contributed by root=2
\= dp[1] dp[1]
\= 1 1 = 1

---

Case 3: Root = 3

Left subtree: 2 nodes → dp[2]
Right subtree: 0 nodes → dp[0]

     3
    /
   1
    \
     2

or

     3
    /
   2
  /
 1

Total contributed by root=3
\= dp[2] dp[0]
\= 2 1 = 2

---

Final Count

Adding all cases:

dp[3] = 2 (root=1)
      + 1 (root=2)
      + 2 (root=3)
      = 5

This visual breakdown is exactly how the DP formula works.