# Elegant Java solution with explanation

• Others have done more efficient solution using Catalan numbers. This solution uses top-down memoization with recursion. A bottoms-up DP will be better for performance and it should be straight-forward to write in case you want a better performance. I will highlight the idea in this explanation. Here is the summary:

1. Assuming we have n = 3, it is made of set {1,2,3}. Since we are constructing a BST, we could choose any node as the root and make another set of BSTs from the remaining of the nodes.
2. So, let us pick up 1 as a root. We will have only one possibility of keeping {2,3} as the right nodes. So the solution for this part will be the no. of unique bsts for n=2
3. Pick 2 as a root. We will have {1} and {3} as two bsts where each one will have only 1 solution.
4. Pick 3 as a root. We will have {1,2} as the left children with a count = 2 for n=2.

This leads to a recursive equation of :
T(n) =

``````  for(int i=1;i<=n;i++) {
//make each one a root.
val += T(i-1)*T(n-i);
}
``````

The base conditions will be T(0)=T(1)=1.

The code is:

``````public int numTrees(int n) {
//+ve values
if(n<=1) {
return 1;
}
int val=0;
for(int i=1;i<=n;i++) {
//make each one a root.
if(map.get(i-1)==null) {
map.put(i-1,numTrees(i-1));
}
if(map.get(n-i)==null) {
map.put(n-i,numTrees(n-i));
}
val += map.get(i-1)*map.get(n-i);
}

return val;
}
``````

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