## Wednesday, February 24, 2016

### LeetCode 95 - Unique Binary Search Trees II

Related: LeetCode 96 - Unique Binary Search Trees I
https://leetcode.com/problems/unique-binary-search-trees-ii/
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
```   1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3
```
confused what `"{1,#,2,3}"` means? > read more on how binary tree is serialized on OJ.
Related LeetCode 96 - Unique Binary Search Trees
X. DFS
https://discuss.leetcode.com/topic/8410/divide-and-conquer-f-i-g-i-1-g-n-i
I just add an HashMap as the cache, but I'm wondering why the algorithm costs more time.
I would say the time complexity would be exponential. Since it can be found out from his code that T(n) = 2*(T(n-1) + T(n-2) + ... + T(1) + T(0)), T(n) should equal to \$O(2^n)\$

T(n)=T(0)T(n-1)+T(1)T(n-2)+...+T(n-1)T(0)
Catalan Number T(n) = C(n,2n)/(n+1), so it's about O(n^(n-1))
http://n00tc0d3r.blogspot.com/2013/07/unique-binary-search-trees_6.html
Think it in a deductive way:
• n=1, one unique BST.
• n=2, pick one value, and the one remaining node can be built as one BST, i.e. Two BSTs.
• ... ...
• n=k, pick one value i, and split the remaining values to two groups: [1 .. i-1] goes to left subtree and [i+1 .. n] goes to right subtree. Then the problem becomes to construct BSTs with left subtree from BST(1, i-1) and right subtree from BST(i+1, n), where BST(1, i-1) and BST(i+1, n) has been computed in previous iterations.
It is easy to get to a recursive solution:
• Given a range [l .. r], if l > r, return a list containing an empty tree.
• Otherwise, for each value k between l and r, inclusively
• recursively compute BSTs in range [l .. k-1] and range [k+1 .. r]
• construct BSTs with root of k, left subtree from BST(1, i-1) and right subtree from BST(i+1, n).
This algorithm runs in exponential time (much greater then the actual total count of unique BSTs) since we recompute BSTs in subrange [i .. j] repeatedly.
``````private ArrayList<TreeNode> genSubTrees(int l, int r) {
ArrayList<TreeNode> trees = new ArrayList<TreeNode>();
if (l > r) { // return an empty tree
} else {
for (int i=l; i<=r; ++i) {
ArrayList<TreeNode> lefts = genSubTrees(l, i-1);
ArrayList<TreeNode> rights = genSubTrees(i+1, r);
for (TreeNode left : lefts) {
for (TreeNode right : rights) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
}
}
}
}
return trees;
}
public ArrayList<TreeNode> generateTrees(int n) {
return genSubTrees(1, n);
} ``````

I start by noting that 1..n is the in-order traversal for any BST with nodes 1 to n. So if I pick i-th node as my root, the left subtree will contain elements 1 to (i-1), and the right subtree will contain elements (i+1) to n. I use recursive calls to get back all possible trees for left and right subtrees and combine them in all possible ways with the root.
``````    public List<TreeNode> generateTrees(int n) {

return genTrees(1,n);
}

public List<TreeNode> genTrees (int start, int end)
{

List<TreeNode> list = new ArrayList<TreeNode>();

if(start>end)
{
return list;
}

if(start == end){
return list;
}

List<TreeNode> left,right;
for(int i=start;i<=end;i++)
{

left = genTrees(start, i-1);
right = genTrees(i+1,end);

for(TreeNode lnode: left)
{
for(TreeNode rnode: right)
{
TreeNode root = new TreeNode(i);
root.left = lnode;
root.right = rnode;
}
}

}

return list;
}``````
There is shared sub problem, but generate method is called every time. So no need to clone at all
``````public List<TreeNode> generateTrees(int n) {
return genTreeList(1,n);
}

private List<TreeNode> genTreeList (int start, int end) {
List<TreeNode> list = new ArrayList<TreeNode>();
if (start > end) {
}
for(int idx = start; idx <= end; idx++) {
List<TreeNode> leftList = genTreeList(start, idx - 1);
List<TreeNode> rightList = genTreeList(idx + 1, end);
for (TreeNode left : leftList) {
for(TreeNode right: rightList) {
TreeNode root = new TreeNode(idx);
root.left = left;
root.right = right;
}
}
}
return list;
}``````

#### X. DP

We probably could view the time complexity from another aspect.
Consider what this algorithm do. It generates possible BST for numbers from 1 to n. It first generate possible BST for [1], then for [1,2], ... then [1,2,...n]. And it traversed each of the results. Thus I would say the total time complexity is equal to the sum of the total number of unique binary trees for [1], [1,2], ... [1,2, ...n]. I don't really know how many unique BST for n numbers, but for unique Binary tree, the number is `(2n)!/((n+1)!n!)`
https://discuss.leetcode.com/topic/12559/java-dp-solution-and-brute-force-recursive-solution
Then @6219221 reminded me it is unnecessary to create the BSTs with all brand new nodes.
Assume you have a list of all BSTs with values from 1 to n-1, every possible way to insert value n only involves changing the right tree (root inclusive) because n is always greater than root.val and the left subtree structure is fixed. So all we gotta do is to create a new copy of the right part of the tree and point the new root.left to the original left subtree. This way we reuse the left tree, which saves time and space.
How to insert Node n into the right subtree?
Given any BST on the n - 1 level, it will be only valid to put n on the root.right, root.right.right or root.right.....right locations and then move the right subtree of n.right...right to become the left child of n, in order to keep n on the right-most position as the greatest value in the tree.
Here is my implementation. Note that I do the dp from [n] back to [n to 1]. Therefore all the right subtree structures are fixed and new values are inserted into the left side, opposite to making BSTs from 1 to [1 to n].
Hi, your solution is not a DP. So there will exist so many duplicate trees created during the recursion, which will waste too much time.
Oh yes. It took me a while to see what you are saying. Subtrees could be reused with the DP approach. Not only it saves time but also space is freed from creating extra nodes of the same value. Although having trees that share branches could be tricky to deal with in the real world, it is the best solution for an algorithm exercise indeed.

Your code is better than mine, but it's not easy to understand why not to clone left, there're some node share,but it doesn't matter,because they are all left node.And it took me some time to understand.there is my solution for more easy to understand.
``````    public List<TreeNode> generateTrees(int n) {
List<TreeNode> res = new ArrayList<>();
for(; n > 0; n--) {
List<TreeNode> next = new ArrayList<>();
for(TreeNode node: res) {
//the special case when Node(n) is root of new tree
TreeNode root = new TreeNode(n);
root.right = node;
//while loop inserts new value to every possible position into the left tree side
while(node != null) {
TreeNode cRoot = new TreeNode(root.right.val);
//clone left subtree
cRoot.left = copyTree(root.right.left);
//reusing - point new root.right to the original right subtree
cRoot.right = root.right.right;
//curr is the cutoff node whose right child will be replaced by the new n
TreeNode curr = getValNode(cRoot, node.val);
//place n as curr's right child, make curr's original right child as the left child of n.
TreeNode tmp = curr.left;
curr.left = new TreeNode(n);
curr.left.right = tmp;

node = node.left;
}
}
res = next;
}
return res;
}
private TreeNode getValNode(TreeNode n, int val) { //find the cutoff node in the new tree
while(n != null) {
if(n.val == val) break;
n = n.left;
}
return n;
}

private TreeNode copyTree(TreeNode root) { //clone the right subtree
if(root == null) return null;
TreeNode cRoot = new TreeNode(root.val);
cRoot.left = copyTree(root.left);
cRoot.right = copyTree(root.right);
return cRoot;
}``````

X. DP 2
https://discuss.leetcode.com/topic/3079/a-simple-recursive-solution/10
Using DP causes two problems:
1. It consumes lots of space, so possible running out of heap space for large n
2. Using DP means you are reusing Subtree[start, end] solution. Which means if two unique BST both contains Subtree[3, 5], you are using the same saved subtree in two different BST. It is not a completely deep copy.

Noticing the repeat computation in the above algorithm gives us a hint of DP: Can we store some intermediate results so as to reuse it rather than recomputing it?

The answer is yes and we can store BSTs of range [i .. i+k] and then for next range [i .. i+k+1] we can reuse previous results!
• Create a table T containing lists of BSTs such that T[il] = a list of BSTs of range [i .. i+l].
• Initialize the table with T[i, 0] which are all single node trees.
• Increasing the size of range from 1 to n-1 and fill up the table.
For each range size l,
•  For each starting value i,
• For each value k in [ii+l], construct BSTs with root of k, left subtree from BSTs of [ik-i-1] and right subtree from BSTs of [k+1i+l-k-1].
• Finally, T[0, n-1] gives us the result of all BSTs.
Exponential time: since we recompute BSTs in subrange [i .. j] repeatedly.

This algorithm sacrifice space for time. Since each subtree is only computed and stored once, the time and space complexities are equal to the total number of unique BSTs, which is the Catalan number as proven in previous post.

There are other ways to build such a table. For example, build up a table of T such that T[ij] = a list of BSTs of range [i .. j]. In that case, for each T[ij] where i > j we need to put an empty tree there.
``````public ArrayList<TreeNode> generateTrees(int n) {
if (n < 1) {
ArrayList<TreeNode> trees = new ArrayList<TreeNode>();
return trees;
}

// T[i,l] contains a list of BSTs of [i .. i+l]
ArrayList<ArrayList<ArrayList<TreeNode>>> allNumTrees = new ArrayList<ArrayList<ArrayList<TreeNode>>>(n);

// init with single node trees
for (int i=1; i<=n; ++i) {
ArrayList<ArrayList<TreeNode>> numTrees = new ArrayList<ArrayList<TreeNode>>(n-i);
ArrayList<TreeNode> trees = new ArrayList<TreeNode>();
TreeNode root = new TreeNode(i);
}

// fill up the table
for (int l=1; l<n; ++l) { // levels
for (int i=0; i<n-l; ++i) { // starting number
ArrayList<ArrayList<TreeNode>> numTrees = allNumTrees.get(i);
ArrayList<TreeNode> trees = new ArrayList<TreeNode>();
for (int k=i; k<=i+l; ++k) { // root value
if (k == i) {
for (TreeNode right : allNumTrees.get(k+1).get(l-1)) {
TreeNode root = new TreeNode(k+1);
root.right = right;
}
} else if (k == i+l) {
for (TreeNode left : allNumTrees.get(i).get(l-1)) {
TreeNode root = new TreeNode(k+1);
root.left = left;
}
} else {
for (TreeNode left : allNumTrees.get(i).get(k-i-1)) {
for (TreeNode right : allNumTrees.get(k+1).get(i+l-k-1)) {
TreeNode root = new TreeNode(k+1);
root.left = left;
root.right = right;
}
}
}
}
}
}

return allNumTrees.get(0).get(n-1);
} ``````

https://leetcode.com/discuss/9790/java-solution-with-dp
result[i] stores the result until length i. For the result for length i+1, select the root node j from 0 to i, combine the result from left side and right side. Note for the right side we have to clone the nodes as the value will be offsetted by j.
Why do we need the clone method, and Why we apply it on the right subtree only!?

This is because for the left nodes, they always start from 1, which have the same values with those in dp[]; While the right nodes, starting at j+1, so they need offset = j+1;
F(i, j) = G(j-1) * G(i-j)
G(n) = F(1, n) + F(2, n) + ... + F(n, n);
G(n) = G(0, n-1) + G(1, n-2) + .. + G(n-1) * G(0)
public static List<TreeNode> generateTrees(int n) { List<TreeNode>[] result = new List[n+1]; result[0] = new ArrayList<TreeNode>(); result[0].add(null); for(int len = 1; len <= n; len++){ result[len] = new ArrayList<TreeNode>(); for(int j=0; j<len; j++){ for(TreeNode nodeL : result[j]){ for(TreeNode nodeR : result[len-j-1]){ TreeNode node = new TreeNode(j+1); node.left = nodeL; node.right = clone(nodeR, j+1); result[len].add(node); } } } } return result[n]; } private static TreeNode clone(TreeNode n, int offset){ if(n == null) return null; TreeNode node = new TreeNode(n.val + offset); node.left = clone(n.left, offset); node.right = clone(n.right, offset); return node; }
Your code is better than mine, but it's not easy to understand why not to clone left, there're some node share,but it doesn't matter,because they are all left node.And it took me some time to understand.
https://leetcode.com/discuss/10254/a-simple-recursive-solution
http://www.programcreek.com/2014/05/leetcode-unique-binary-search-trees-ii-java/
https://leetcode.com/discuss/24305/divide-and-conquer-f-i-g-i-1-g-n-i
 ```public List generateTrees(int n) { return generateTrees(1, n); } public List generateTrees(int start, int end) { List list = new LinkedList<>();   if (start > end) { list.add(null); return list; }   for (int i = start; i <= end; i++) { List lefts = generateTrees(start, i - 1); List rights = generateTrees(i + 1, end); for (TreeNode left : lefts) { for (TreeNode right : rights) { TreeNode node = new TreeNode(i); node.left = left; node.right = right; list.add(node); } } }   return list; }```
http://gongxuns.blogspot.com/2013/01/leetcodeunique-binary-search-trees-ii.html
```    public ArrayList<TreeNode> generateTrees(int a, int b){
ArrayList<TreeNode> res = new ArrayList<TreeNode>();

if(a>b){
}else if(a==b){//
}else{
for(int i=a;i<=b;i++){
ArrayList<TreeNode> temp1 = generateTrees(a,i-1);
ArrayList<TreeNode> temp2 = generateTrees(i+1,b);

for(TreeNode n:temp1){
for(TreeNode m:temp2){
TreeNode temp= new TreeNode(i);
temp.left=n;
temp.right=m;
}
}

}
}
return res;
}```
``````def generateTrees(self, n):
def node(val, left, right):
node = TreeNode(val)
node.left = left
node.right = right
return node
def trees(first, last):
return [node(root, left, right)
for root in range(first, last+1)
for left in trees(first, root-1)
for right in trees(root+1, last)] or [None]
return trees(1, n)
``````
Or even just four lines, if it's not forbidden to add an optional argument:
``````def node(val, left, right):
node = TreeNode(val)
node.left = left
node.right = right
return node

class Solution:
def generateTrees(self, last, first=1):
return [node(root, left, right)
for root in range(first, last+1)
for left in self.generateTrees(root-1, first)
for right in self.generateTrees(last, root+1)] or [None]``````
http://www.jiuzhang.com/solutions/unique-binary-search-trees-ii/
https://leetcode.com/discuss/31127/a-simple-bottom-up-dp-solution