# Simple Recursion Java Solution with Explanation

• The idea is to use each number i as root node, then the left branch will be what's less than i, the right branch will be what's larger than i. The total number of distinct structure is their product. Thus, sum up the product for all numbers. Use a map to memorize the visited number.

``````public class Solution {
public int numTrees(int n) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0,1);
map.put(1,1);
return numTrees(n, map);
}

private int numTrees(int n, Map<Integer, Integer> map){
// check memory
if(map.containsKey(n)) return map.get(n);
// recursion
int sum = 0;
for(int i = 1;i <= n;i++)
sum += numTrees(i-1, map) * numTrees(n-i, map);
map.put(n, sum);
return sum;
}
}``````

• Your solution works very slow, you should memoize the results that you've already calculated

``````public class Solution {
public int numTrees(int n) {
// base case
if(n <= 1){return 1;}
if (memo[n] != -1) return memo[n];
// recursion
int sum = 0;
for(int i = 1;i <= n;i++)
sum += numTrees(i-1-0) * numTrees(n-i);
return memo[n] = sum;
}
}``````

• By the way, this formula known as Catalan numbers formula as well

• but int case, numTree(0), it should be 0 i think.. because it has the limitation of 1 ~ n ...doesn't matter to this case as if the case 0 been paid attention

• I submit the same code as you and time limit exceeded when n = 19.

• Thank you for pointing it out. It seems the test case was changed afterwards. The original DFS solution will run in O(2^n) time. When apply path memorizing, the DFS will run in O(n^2) time. Please see the updated code. Hope that helps!

• share my similar solution.

``````    private int[] counts = null;

public int numTrees(int n) {
counts = new int[1 + n];
return calNumTrees(n);
}

private int calNumTrees(int n) {
if (counts[n] != 0) return counts[n];   // cache

if (n <= 1) return 1;

int total = 0;
for (int i = 1; i <= n; ++i) {
total += calNumTrees(i - 1) * calNumTrees(n - i);
}
counts[n] = total;