# Divide-and-conquer. F(i) = G(i-1) * G(n-i)

• This problem is a variant of the problem of Unique Binary Search Trees.

I provided a solution along with explanation for the above problem, in the question "DP solution in 6 lines with explanation"

It is intuitive to solve this problem by following the same algorithm. Here is the code in a divide-and-conquer style.

``````public List<TreeNode> generateTrees(int n) {
return generateSubtrees(1, n);
}

private List<TreeNode> generateSubtrees(int s, int e) {
if (s > e) {
return res;
}

for (int i = s; i <= e; ++i) {
List<TreeNode> leftSubtrees = generateSubtrees(s, i - 1);
List<TreeNode> rightSubtrees = generateSubtrees(i + 1, e);

for (TreeNode left : leftSubtrees) {
for (TreeNode right : rightSubtrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
}
}
}
return res;
}
``````

• Seems it is not a DP, but just a divide-and-conquer one. Because algorithm could generate the same subtree for twice as it did not record the tree it generated before.

• Yes, it is a divide-and-conquer solution, as I mentioned in the title of this post.

• I tried your code and found when input n is 0, the expected output is [], but yours is [[]]. I think you need to add just one case control.

• add one line case control as following is accepted

public List<TreeNode> generateTrees(int n) {

if(n==0) return new LinkedList<TreeNode>(); //here is new line

return generateSubtrees(1, n);

}

• I just add an HashMap as the cache, but I'm wondering why the algorithm costs more time.

public class Solution {

``````Map<List<Integer>,List<TreeNode>> hm = new HashMap<>();

public List<TreeNode> generateTrees(int n) {
if(n == 0) return res;
return generateSubtrees(1, n);
}

private List<TreeNode> generateSubtrees(int s, int e) {
if (s > e) {
return res;
}

for (int i = s; i <= e; ++i) {
List<Integer> leftIndex = new ArrayList<>();
List<Integer> rightIndex = new ArrayList<>();
List<TreeNode> leftSubtrees,rightSubtrees;
if(hm.get(leftIndex) == null){
leftSubtrees = generateSubtrees(s, i - 1);
hm.put(leftIndex,leftSubtrees);
}
else leftSubtrees = hm.get(leftIndex);

if(hm.get(rightIndex) == null){
rightSubtrees = generateSubtrees(i + 1, e);
hm.put(rightIndex,rightSubtrees);
}
else rightSubtrees = hm.get(rightIndex);

for (TreeNode left : leftSubtrees) {
for (TreeNode right : rightSubtrees) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
}
}
}
return res;
}
``````

}

• how would you think its complexity?

• @Scarlett_comeup
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)\$

• Why we really the case: if(s > e)? I tried run the code without this case. Then I get the empty list for final result. Could anyone tell me why it is that?

• @liaison can you please explain how recursion works here exactly? It is little difficult to visualize how all the trees will be generated from this.

• @YaokaiYang Catalan number Cn ~4^n/n^(3/2). I agree with exponential complexity.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.