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)