## Twitter Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

@vegeek: I think the Catalan number represents the total number of Full Binary Trees and this question asks for binary tress in general. Please correct me if I am wrong.

@nimbus

The number of possible trees that can be made with n number of keys are:

T(n)=(2n)!/(n)!*(n+1)!

So it is 42

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).

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)`

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)}

The recurrence relation should be as follows

- Anonymous August 06, 2013T(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