Question

link

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

Stats

Frequency 1
Difficulty 3
Adjusted Difficulty 3
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This seems like an easy recursion question, however it will result in many repeated recursion calls.

To avoid repeated recursion, use Dynamic Programming.

Solution

First code below is my solution. It is a standard recursion solution, but it’s not good. The run time is 30ms more than next code.

Second code is DP solution, where the previous answers are saved and used forfuture calculation. This is the best solution for this question, and I learnt it from this blog.

Code

First code

public int numTrees(int n) {
    if (n <= 1) return 1;

    int total = 0;
    if (n % 2 == 0){
        for (int i = 0; i <= n / 2 - 1; i ++ ){
            // i is all the possible number of nodes on the left
            total += 2 * numTrees(i) * numTrees(n-i-1);
        }
    } else {
        for (int i = 0; i <= (n-1) / 2 - 1; i ++ ){
            // i is all the possible number of nodes on the left
            total += 2 * numTrees(i) * numTrees(n-i-1);
        }
        total += Math.pow(numTrees((n-1)/2), 2);
    }
    return total;
}

Second code

public int numTrees(int n) {
    int[] table = new int[n + 1];
    table[0] = 1;
    table[1] = 1;
    for (int i = 2; i <= n; i++) {
        int sum = 0;
        for (int j = 1; j <= i; j++) {
            int left = j - 1;
            int right = i - j;
            sum += table[left] * table[right];
        }
        table[i] = sum;
    }
    return table[n];
}