Problem:
Given an integer n, return how many unique BST's (binary search trees) with values 1, 2, 3 ... n.
For Example:
Given integer: 3
Answer: 5
Explain:
The unique BSTs with values 1 2 and 3 are the following 5:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Solution:
Given 1 2 3, we have 3 choices for the root node. The root node can be the element at index i from 0 to 2, each choice will give us a new group of new BSTs. The number BST created by each choice is marked as F(n, i). So the total number of unique BSTs is the following:
G(n) = Sum(F(n, i))
where i range from 0 to n-1.
For a given F(n, i), the root node i divide the 1 to n array into left and right subtree. The left subtree has i - 1 elements, the right tree has n - i elements.
Left half has G(i - 1) possible choices, the right half has G(n - i) choices,
So F(n, i) = G(i - 1)*G(n - i)
Finally, our formula is:
G(n) = Sum(G(i - 1)*G(n-i)) where i range from 1 to n.
We already know the base Case
G(0) = 1
G(1) = 1
What's left is use dynamic programming to find the G(2), G(3) .... G(n).
class Solution {
public static void main(String...args) {
System.out.println(enumerate(3));
}
public static int enumerate(int size) {
int[] g = new int[size + 1];
g[0] = 1;
g[1] = 1;
for(int n = 2; n <= size; n++) {
for(int j = 1; j <= n; j++) {
g[n] += g[j-1]*g[n-j];
}
}
return g[size];
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
public static void main(String...args) {
System.out.println(enumerate(3));
}
public static int enumerate(int size) {
int[] g = new int[size + 1];
g[0] = 1;
g[1] = 1;
for(int n = 2; n <= size; n++) {
for(int j = 1; j <= n; j++) {
g[n] += g[j-1]*g[n-j];
}
}
return g[size];
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
There are 2 for loops, so the time complexity is O(N^2). We store the middle value of G(i) where i ranges from 0 to n. So the space complexity is O(N).
