LeetCode 96.

Question

Given an integer n, return the number of structurally unique BST's (binary search trees) 
which has exactly n nodes of unique values from 1 to n.

Example

• Example 1:

  Input: n = 3

  Output: 5

• Example 2:

  Input: n = 1

  Output: 1

Intuition

As I saw this question, I was wondering if I can breakdown this problem into sub-problems.

Every BST, or in general Tree, must have its left and right node(sub-tree) whatever they’re empty.

Obviously from the description we can tell that the answer should be the multiplication of the permutation of left and right sub-tree.

Additionally, we can assume whatever nodes’ value are, if they are unique then the answer should be the same if two of trees have same number of nodes.

For instance, both TreeA[1,2,5] and TreeB[2,3,6] has the answer 5.

Approach

• Declare an array to keep the answer: result[n + 1]
• Set initial value of the array: result[0] = 1, result[1] = 1, result[2] = 2
• Do the iteration from bottom to top because Tree[i] will use Tree[i-1] to Tree[1]

Complexity

• Time complexity: O(n^2)

• Space complexity: O(n)

Code

class Solution {
    public static int numTrees(int n) {
        if (n == 1) return 1;
        int[] result = new int[n + 1];
        Arrays.fill(result, 1);
        result[2] = 2; // initial value

        for (int i=3; i<=n; i++) {
            int temp = 0;
            for (int j=0; j<i; j++) {
                // // minus one because the root node counts
                temp += result[j] * result[i - j - 1]; 
            }
            result[i] = temp;
        }

        return result[n];
    }
}

Check out the description of this problem at LC 96.