LeetCode: Unique Binary Search Trees Calculation

Question

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example, Given n = 3, there are a total of 5 unique BST's.

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

I've got this solution:

/**
 * Solution:
 * DP
 * a BST can be destruct to root, left subtree and right subtree.
 * if the root is fixed, every combination of unique left/right subtrees forms
 * a unique BST.
 * Let a[n] = number of unique BST's given values 1..n, then
 * a[n] = a[0] * a[n-1]     // put 1 at root, 2...n right
 *      + a[1] * a[n-2]     // put 2 at root, 1 left, 3...n right
 *      + ...
 *      + a[n-1] * a[0]     // put n at root, 1...n-1 left
 */
int numTrees(int n) {
    if (n < 0) return 0;
    vector<int> trees(n+1, 0);
    trees[0] = 1;

    for(int i = 1; i <= n; i++) 
        for (int j = 0; j < i; j++) 
            trees[i] += trees[j] * trees[i-j-1];

    return trees[n];
} 

Because this answer was given out too long ago to touch this 'dragonmigo' guy. This solution is accepted and my problem is:

In the comment, trees[0] refers to case 1. (0+1 = 1)

If so, trees[n-1] should refer to case 1...n rather than the case 2...n. (n-1+1=n)

Is my thinking wrong?

p.s. I know this is actually a Catalan number and I know the algorithm using the deduction formula to solve it.

Answer 1

trees[n] is the number of trees with exactly n nodes. There is 1 trees with 0 nodes, hence trees[0] == 1. For a given n > 0 there is a root node and two children trees whose total size is: n-1

• trees[n-1] possible trees on the left and trees[0] on the right
• trees[n-2] possible trees on the left and trees[1] on the right
• ...
• trees[1] possible trees on the left and trees[n-1-1] on the right
• trees[0] possible trees on the left and trees[n-1] on the right

When you have trees[k] possible trees on the left, and trees[l] on the right, it makes trees[k]*trees[l] possible combinations. This means:

trees[n] = trees[n-1]*trees[0]
         + trees[n-2]*trees[1]
         + ...
         + trees[1]*trees[n-2]
         + trees[0]*trees[n-1]

The outer loop compute all trees[n]. The inner loop compute each of these using the decomposition I shown above (and the computations of all the values before n).