# Did you deduce a formula of the tree numbers f(n) or just simulate a tree generation process?

• i simulate a BST generation, and got TLE.

• You should probably explain more how you simulate your BST generation. As far as I knew, you are not required to deduce the formula in order to get Accepted.

• You need to use formula with recursion to calculate the number without exceeding.
Check: http://cs.lmu.edu/~ray/notes/binarytrees/

You should not need to simulate entire BST generation.
That will be done for part II.

• Simulation is not necessary

Even recursive function can pass, test cases are too weak!

idea:
choose i to be the root, then there i -1 numbers in the left child tree, n - i numbers in the right child tree, calculate child tree recursively

f(0) = 1

f(1) = 1

f(2) = 2

f(n) = f(n-1) * f(1 -1) + f(n-2) * f(2 -1) + f(n-3) * f(3-1) + ... + f(n-n) * f(n-1)

In addition, lookup table can be used to improve performance!

• Consider about Catalan Number.

• Yes I had the same idea. I memoize results for i = 1...n and in every iteration I uses memoized values from former steps.

• class Solution {
public:
int numTrees(int n) {
long long ans = 1;
for(int i = 1; i <= n; ++ i)
ans  = ans * 2 * (2 * i - 1) / (i + 1);
return (int) ans;
}
};

It is base on the iterative formula of Catalan number.
C(i+1) = C(i) * 2 * ( 2 * i - 1 ) / (i + 1);

• of course we dont need, it is not about memorization

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