LeetCode: Unique Binary Search Trees Calculation

algorithm, binary-search-tree, catalan

Solution

`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`).

Problem

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.

Original source