Reference: LeetCode
Difficulty: Medium

My Post: [Java] Recursion & Iteration Solutions (DP, Clone, Memoization)

Problem

Given an integer $n$, generate all structurally unique BST’s (binary search trees) that store values 1 ... n.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

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

Analysis

Recursion

If we directly apply the solution in 96. Unique Binary Search Trees, we have an incorrect result. Consider the following example.

1
2
3
4
5
6
7
n = 5, i = 3
2 left nodes: [1, 2]
2 right nodes: [4, 5]

n = 10, i = 8
7 left nodes: [1, 2, 3, 4, 5, 6, 7]
2 right nodes: [9, 10]

As you can see, although there are still 2 nodes in the right subtrees, the values are not the same. In the previous approach, it did not handle this situation.

So rather than passing a parameter n (number of nodes), we now pass down two parameters lo and hi indicating the range of values of a tree.

For example, generateTrees(1, 5) generate trees whose values range from 1 to 5, and each of them has a chance to be the root, which also includes the information of number of nodes n. Say when the root is 3, we calculate generateTrees(1, 2) and generateTrees(4, 5).

Note: When n == 0, it returns [] instead of [[null]].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new ArrayList<>();
}
return generateTrees(1, n);
}

private List<TreeNode> generateTrees(int lo, int hi) {
int n = hi - lo + 1;
if (n == 0) {
List<TreeNode> L = new ArrayList<>();
L.add(null);
return L;
}
List<TreeNode> result = new ArrayList<>();
for (int i = lo; i <= hi; ++i) {
List<TreeNode> leftSubtrees = generateTrees(lo, i - 1);
List<TreeNode> rightSubtrees = generateTrees(i + 1, hi);
for (TreeNode leftSub : leftSubtrees) {
for (TreeNode rightSub : rightSubtrees) {
TreeNode newTree = new TreeNode(i);
newTree.left = leftSub;
newTree.right = rightSub;
result.add(newTree);
}
}
}
return result;
}

Time: It is at most bounded by $O(N \times N!)$. A tighter bound would be Catalan number times $N$ since we’ve done $N$ times, which is $N \times G_N = O(N\times\frac{4^N}{N^{3/2}}) = O(\frac{4^N}{N^{1/2}})$.
Space: $O(N \times G_N) = O(\frac{4^N}{N^{1/2}})$

DP (Clone)

Reference: link

Let’s denote tree[i] as the list of trees of size i. Think of tree[i] as our building blocks for a larger tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
Example: n = 3

tree[0]:
null

tree[1]:
[1]
[2]
[3]

tree[2]:
[1 2]
1
\
2 // 2 structures
2
/
1
[2 3]
2
\
3
3
/
2 // [1 3] is not possible

tree[3]: // (based on tree[1], tree[2])
3
/
[1 2]
1
\
[2 3]
2
/ \
[1] [3]

So we can compute all possible trees for tree[1], tree[2], …, then we can construct tree[n] by previous results.

For a small n = 3 , we notice that when we calculate tree[2] we want all possible combinations for tree[2] ([1 2], [2 3]). Furthermore, if we have a large n = 100, we want all the combinations as follows [1 2], [2 3], [3 4], …, [99 100] (each of them has two structures).

Since these trees have the same two types of structures:

1
2
3
x       y
\ /
y x

We can actually construct all the trees by [1 2] plus some constant, say offset. For example, [5 6] can be constructed as follows:

1
2
3
4
5
6
7
1    +4    5
\ \
2 +4 6
------------------
2 +4 6
/ /
1 +4 5

Say the problem is n = 100. During the execution of the algorithm when i = 98, we want to get all possible trees for i = 98 as the root. The size of the left subtree is 97 and the subtree is picked from tree[97]; the size of the right subtree is 2 and the subtree is picked from tree[2].

For the left subtree, we already have tree[97] computed as [1 2 3 ... 97].

For the right subtree, we want [99 100], which can be computed by [1 2] plus offset = 98.

1
2
3
4
5
6
7
1    +98    99
\ \
2 +98 100
------------------
2 +98 100
/ /
1 +98 99

Therefore, given a tree root, we can generate a new tree by cloning with an offset.

1
2
3
4
5
6
7
8
9
10
// adding offset to each node of a tree root
private TreeNode clone(TreeNode root, int offset) {
if (n == null) {
return null;
}
TreeNode node = new TreeNode(root.val + offset);
node.left = clone(root.left, offset);
node.right = clone(root.right, offset);
return node;
}

For input n, the result we want is tree[n] ([1 2 3 ... n]). Here is the code for generateTrees(n):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<TreeNode> generateTrees(int n) {
List<TreeNode>[] tree = new ArrayList[n + 1];
tree[0] = new ArrayList<>();
if (n == 0) {
return tree[0];
}
tree[0].add(null);
// Calculate all lengths
for (int len = 1; len <= n; ++len) {
tree[len] = new ArrayList<>(); // contains all trees we construct
// Consider each as the root
for (int i = 1; i <= len; ++i) {
int leftSize = i - 1;
int rightSize = len - i;
for (TreeNode leftTree : tree[leftSize]) [
for (TreeNode rightTree : tree[rightSize]) {
TreeNode tree = new TreeNode(i);
tree.left = leftTree; // left subtree requires no cloning
tree.right = clone(rightTree, i); // add i as the offset
tree[len].add(tree);
}
]
}
}
return tree[n];
}

Time: N/A (I don’t know T_T)
Space: N/A (I don’t know T_T)

DP (2D)

Judge: 1ms, faster than 99.95%. I have nothing to say.

Here is the code I wrote:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new ArrayList<>();
}
List<TreeNode>[][] g = new ArrayList[n + 1][n + 1];
// init
List<TreeNode> nullList = new ArrayList<>(); nullList.add(null);
g[0][0] = nullList;
for (int k = 1; k <= n; ++k) { // g(0, k)
g[0][k] = nullList;
}
for (int k = 1; k <= n; ++k) { // diagonal: one node (itself)
List<TreeNode> oneList = new ArrayList<>(); oneList.add(new TreeNode(k));
g[k][k] = oneList;
}
for (int k = 1; k <= n; ++k) { // one node above diagonal: nullList
g[k][k - 1] = nullList;
}
// dp
for (int i = n - 1; i >= 1; --i) {
for (int j = i + 1; j <= n; ++j) {
List<TreeNode> result = new ArrayList<>();
for (int k = i ; k <= j; ++k) { // for each k as root [i, j]
List<TreeNode> leftList = (k - 1 <= n) ? g[i][k - 1] : nullList;
List<TreeNode> rightList = (k + 1 <= n) ? g[k + 1][j] : nullList;
for (TreeNode left : leftList) {
for (TreeNode right: rightList) {
TreeNode newTree = new TreeNode(k);
newTree.left = left;
newTree.right = right;
result.add(newTree);
}
}
}
g[i][j] = result;
}
}
return g[1][n];
}

Time: N/A (I don’t know T_T)
Space: N/A (I don’t know T_T)


Comment