Twitter Interview Question
Software Engineer / DevelopersCountry: 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