CareerCup

The recurrence relation should be as follows
T(n) = T(i) * T(n -1 - i) where i ranges from 0 to n - 1

It should a product of T(i) and T(n -1 - i) and not addition

Catalans numbers?

t(n)= summation of t(i)+t(n-1-i) with i varying from 2 to n-1

The recurrence relation of a binary tree is given by the expression:
T(n)=T(k)+T(n-k-1)+c.
Here k are the number of nodes of the left subtree and n-k-1 are the number of nodes of the right subtree. Also for a complete binary tree
T(n)=T(n-1)+T(n-1)+c. So it is T(n)=2T(n-1)+c. So as it can be seen that the recurrence relation is a function of linear n. So the time complexity of traversal of a tree is O(n). (That is a whole tree both left and right).

I think the solution should be:

T(0) = 0
T(1) = 1
T(2) = 2
T(3) = 2
T(n) = SUM( T(i)*T(n-1-i) ) where i ranges from 1 to n - 2

T(N)= N!

Given a pre-order traversal,

1, 2, 3, 4, ... n

, the first character is always the root. The remaining string can be broken at any place into a left subtree and a right subtree. This remaining string is (n-1) characters long. If you break it at the i-th position, then the left subtree has T(i) ways of being constructed, and the right subtree has T(n-1-i) ways of being constructed. Therefore,

T(n) = Sum over i from i=0 to i=n-1 T(i)*T(n-1-i)

2^(n-1)

Standard Dynamic Programming problem.

suppose you know the number of different way to construct BST with 0~N-1 nodes T(0),T(1)......T(N-1).

If we add one more node. we could have "i" nodes on left and "N-1-i" nodes on the right tree, since it is BST, the number "i" uniquely determines the sets of number on Left tree / root / right tree.
therefore the answer T(N) = sum_{all_i}{T(i) * T(N-1-i)}

T(k) = 2T(k-1) + Sum_{1<=i<=k-2} T(i)*T(k-1-i)

Binary trees or binary search trees?