[LeetCode] 96. Unique Binary Search Trees

Posted on | In

Problem

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

Example:

1
2
3
4
5
6
7
8
9
10
Input: 3
Output: 5
Explanation:
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

Explanation

  1. We can use dynamic programming to solve this problem.

  2. Dynamic state is a one dimensional array, dp[n] means when input is n, the total number of unique BST.

  3. Dynamic init is dp[0] = 1, dp[1] = 1. For example, when n is 1, we only have one way to struct the unique BST.

  4. Dynamic function. When n = 2, the total number of unqiue BST is 2, in other word, the root node can be 1, right node can be 2; or root node is 2, left node is 1. When n = 3, we have three cases: when root node is element 1, there is 0 node on the left and there are 2 nodes on the right; when root node element is 2, there is 1 node on the left and 1 node on the right; when root node is element 3, there are 2 nodes on the left and 0 node on the right. We can illustrate it below:

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

  5. From the above illustration, input n=3, when root node is element 1, it can only have 0 node on the left and 2 nodes on the right, and there are 2 unique ways because dp[0] = 1, dp[2] = 2, and 1 * 2 = 2. When root node is element 2, there is one node on the left and one on the right, and there is 1 unique way because dp[1] = 1, 1 * 1 = 1. When root node is element 3, there are two node on the left and zero node on the right, and there are 2 unique ways because dp[2] = 2, dp[0] = 1, 2 * 1 = 2. Therefore, when input is 3, we have dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0] = 5 unique ways. So, when input is n, if there is 0 node on the left, then there are n-1 node on the right because we need to subtract there is 1 root node.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numTrees(int n) {
        if (n < 1) return 0;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j]*dp[i-1-j];
            }
        }

        return dp[n];
    }
}