Amazon Sabre Holdings Interview Question
Software Engineer / DevelopersA catalan number gives the structurally different binary trees not binary trees which differ in values.
For ex: take 3 nodes. (2n)!(n+1)! = 30 binary trees can be formed.
Let see how:
nodes are A, B and C.
First A as root node,
B can be Left/Right child and similarly C can be Left/Right child so, total 4.
A->B->C , A->C->B can be Left/Right so, total 4.
and finally A left B and right C, A left C and right B. so total 2.
Total trees with A as root node is 10.
similarly for B and C . 10 + 10 + 10.
Assuming values in array are unique
Let there are n elements in array
one can select a root node in n different ways from this list
when root has been selected then array have n-1 elements left
one can select next element in n-1 different ways and for this node we have 2 possible positions
so no of ways for placing second node will be 2 (n-n1)
asuming we have
root
/ \
second
selected
node
/\
clearly third node can be selected in n-2 different ways and 3 possible positions for this node
means 3(n-3) ways for third node
following up in above manner
using all the n nodes from array one can make a binary tree in
n + 2(n-1) + 3(n-2) + 4(n-3)+......+n*1 ways
Please help what will be sum of this series
Also suggest for improvement if possible
little correction to your solution. It should be
n * 2(n-1) * 3(n-2) * 4(n-3)*......* n*1 ways
which comes to (n!)^2
No.. it is wrong.. work out yourself before posting answers and saying "awesome solution"
With 3 nodes you can get 30 unique Binary trees..
from your formula it is 3!^2 = 36 which is wrong..
lets say n=3
no. of binary trees without considering the order of elements will be 2nCn / n+1 (this gives only the different possible orientations of the nodes)
now we can use the array to permutate each element in each orientation this gives:
(2nCn / n+1 ) * n! = 30.
I think if the elements of the array are unique .... all 30 binary trees will also be unique.....
in case n = 3, there are only 5 structures instead of 6, since there is one duplicate.
the solution could work upon proper change.
For the number of unique binary tree, we can recursively solve the problem.
Obviously, S[1] = 1, and S[2] = 2, let S[0] = 1,
For an array with N unique elements, we first choose one element as root. There are n elements which we can choose from. Then we divide the unchosen n-1 elements into two groups. each group may contains (0, n-1) elements, or (1, n-2) elements ... or ( (n-1)/2, n -1 - (n-1)/2) elements. The unique binary trees composed by elements in each group can either be the left or right subtree, not important if we want to count the overall unique binary trees.
So the total number of unique trees are:
S[n] = n ( S[0]*S[n-1]*C(0,n-1) + S[1]*S[n-2]*C(1,n-1) + S[2]*S[n-3]*C(2,n-1) + ... + S[(n-1)/2]*S[n - 1 - (n-1)/2])
where C(i, n-1) is the combination operation (n-1)!/[i!*(n-1-i)!]
well, yes, its a Catalan's number for BTree if we strictly differ left and right children.
- celicom May 15, 2011Wonder, whats the number of topologically unique BTrees (where rotation of L/R nodes is allowed)?
Ankit, Amazon probably expected from you this kind of analysis: link to comeoncodeon.wordpress.com/2010/04/13/number-of-binary-trees/