Amazon Interview Question Software Engineer / Developers
Thanks, Excellent! This is a new one for me.
So in the context of a Catalan Number the question means the number of binary trees with n nodes.
Which for n=(0,1,2,3,4) is (1,2,5,14,42) which is the Catalan number Cn
Cn = 1/(n+1)(2n n) [where (2n n) is the number of combinations of 2n elements taken n at a time]
(see http://mathworld.wolfram.com/BinaryTree.html )
In that case it looks like the first answer proposed is correct, but the second by vindhyavasini is not correct.
If it is correct I don’t understand why you would have
T(C)n*n!
if T(C)n is the Catalan number then the correct answer is
T(C)n not T(C)n*n!.
This should be correct with one clarification. The value n is the height of the tree, not the number of nodes. So the arrangements or permutations of a binary tree of height n=1,2,3,... is 1,2,5,... which is the Catalan Number.
Truly speaking, the question contains nothing about whether a tree is full or not. If the tree is not full then Cataln number is not applicable here, is it?
In case of Binary Trees- number of different non-isomorphic structures: (2^n - n ), n is number of nodes
In case of Binary Search Trees- number of different non-isomorphic structures = Catalan Numbers
isomorphic structures are those where ordering ( left/right matters ) ( refer geeksforgeeks)
It is not clear what is meant by this question and the answer given by anonymous doesn't make it any clearer. If you have n number of elements, how many binary trees can be formed? The obvious answer is you can have n binary trees, each with one element or just a root. Or does the questioner mean how many internal vertices do you have if there are n elements? Which for a full binary tree is i=n-1/2, where i is the number of internal vertices. Or does the questioner mean what is the height of the binary tree if you have n elements? Which is ceiling (log(n)), where log is log base 2. Or the questioner means, what?
total no of nodes in a tree with n height T = sum(i=1 to n) (n*2^(n-1))
no of binary trees: select n positions to fill out of these T places=T(P)n=T(C)n*n!
There is a simpler formulation for the total number of nodes in a full binary tree with height n.
T= 2^(n+1)-1.
Your answer seems to imply that the question regards the number of permutations with T elements, but I can’t make sense of your answer. If you had T elements and you wanted to know how many permutations of T elements taken n at a time you have
(T!/(T-n)!)
This seems to be different from your answer of
T(C)n*n!
but I’m not sure what you mean by this statement. What does T(C)n mean?
boss, P: permutation
C: combination
u are right, answer is: T(C)n*n! = T!/(T-n)!
i know the way i have put answer, that makes question look very simple, may be i have misunderstood something, correct me in case i m wrong
I’m not a boss, or expert, just trying to understand the question and what a reasonable, hopefully correct, answer is to be better prepared for programming interview hell.
Based on how you defined T as T=total number of nodes, then T!/(T-n)! is not the correct answer. T!/(T-n)! is just the number of permutations of T objects taken n at a time and that is not the Catalan number. I think we just have a communication problem.
Check out the link at
http://mathworld.wolfram.com/BinaryTree.html
It has a nice diagram about the middle of the page which I think makes it clearer.
The solution is by definition, assuming this poorly worded question is intended to be about the Catalan number. That seems to be the most reasonable assumption. But, the intent of the question could be entirely different.
Did you look at the web page referenced, specifically, the web page at the following URL?
http://mathworld.wolfram.com/BinaryTree.html
That’s how the solution was determined.
The solutions don't consider the fact that 2 trees with the same structure, but different values in different positions are actually different. Is that the intention of the question. If it is not the case, I think the solution is (n!)^2
I disagree, assuming the question is about the Catalan number which implies that n refers to the number of nodes, but even if you treat it as n values. The Catalan number gives you the number of binary trees.
For example, consider the following set of key values {B, C, H}. There are six different permutations of this set:
1. B, C, H
2. B, H, C
3.C, B, H
4. C, H, B
5. H, C, B
6. H, B, C
If you insert each permutation into a binary tree, you get five distinct binary trees or the Catalan number for three nodes. The third and fourth permutations result in the same binary tree which is why you have five binary trees instead of six. So the Catalan number answers the question.
How many different binary trees are there for a set n of key values?
Consequently you can reasonably make the argument that the Catalan number implicitly considers the values of the nodes. I don’t see any way your solution of (n!)^2 works, it certainly doesn’t answer the question of the number of binary trees you get with n values when n=3.
If you haven’t reviewed the previously mentioned references, see the following URLs for a more detailed explanation. It might help clear things up for you.
http://mathworld.wolfram.com/CatalanNumber.html
http://mathworld.wolfram.com/BinaryTree.html
Hey Michael,
For n=2 Catalan number is also 2.
e.g., i have 5, 10 as the 2 numbers. I can actually produce 4 different binary trees
Root 5: Left Child: 10
Root 5: Right Child: 10
Root 10: Left Child: 5
Root 10: Right Child: 5
My question is if the question expects to make this distiction or not?
Hey Somebody,
I don’t know, but I will make a couple of observations. If you do a preorder, inorder or postorder traversal of the four trees in your example, you only get two permutations {10,5} and {5,10} which is the Catalan number. Secondly, the term binary tree is often synonymous with binary search tree (BST). I think it is more common to treat binary trees as BSTs because a BST defines useful rules for utilizing the tree,i.e., searching a tree for a node.
Treating a binary tree as a BST seems to be especially true when the nodes have a value. Otherwise how do you treat the value? What are the rules for inserting a node into a tree? What are the rules for searching for a node in the tree?
Once you treat it as BST then you only have the Catalan number of binary trees. Also if the nodes don’t have a value or label they are anonymous and you still only have the Catalan number of binary trees.
The original question seems to imply the nodes were anonymous and don’t have any key value, but that’s just my interpretation because that’s what makes sense to me and this is how I would probably present my argument if I were asked this question in an interview.
So in the context of an interview it’s possible there isn’t any single correct answer. Your answer could be correct and I could be completely off base. In an interview you can always ask for clarification and we don’t have that luxury, we are dependent on whoever originally posted the question giving that clarification.
int findNoTree(int low ,int high)
{
int sum=0;
if(low<=high)
{
for(int k=low;k<=high;k++)
{
if(k==low)
sum+=findNoTree(low+1,high);
else
{
if(k==high)
sum+=findNoTree(low,high-1);
else
sum=sum+findNoTree(low,k-1)*findNoTree(k+1,high);
}
}
return sum;
}
return 1;
}
call this function with findNoTree(0,num) ...num is the value of no of nodes in the tree....
O/p : total no. of trees will be equal to the catalan number
Well the purpose of this problem is not to use combinatorics.
Say F(n)=no of different binary trees with n nodes.
Fix one root node and now we will have n-1 nodes.These n-1 nodes need to be arranged around the pivotal root node.
Sum of (F(i)*f(n-i-1)) for i=1 to n-1 might solve ur problem
I guess the question is pretty clear. How many different binary trees possible with n different numbers. It has to take in to account both the different possible configurations and different possible ordering of the numbers.
Different possible configurations = Catalan number = Cn = (2n)! / ( (n+1)! n!)
For each of the above configurations, #possible orderings = n!
Hence, total poss binary trees = Cn * n! = (2n)! / (n+1)!
there are n^(n-2) trees possible with n vertices (Cayley formula).
http: //en.wikipedia.org/wiki/Cayley%27s_formula
And for every tree there are n way to pick root. So in my opinion there are n^(n-1) ways possible.
Verify with lower values:
n=2 then number of trees = 2 and also the formula gives 2^(2-1)=2
n=3 formula gives 3^(3-1) = 9 can you verify by manually drawing all possible tree with 3 node?
/*
For the key values 1...numKeys, how many structurally unique
binary search trees are possible that store those keys.
Strategy: consider that each value could be the root.
Recursively find the size of the left and right subtrees.
*/
int CountTrees(int num)
{
if(num <= 1)
return 1;
else
{
// there will be one value at the root, with whatever remains
// on the left and right each forming their own subtrees.
// Iterate through all the values that could be the root.
int sum = 0;
int left, right, root;
for(root=1 ; root<=num ; root++)
{
left = CountTrees(root - 1);
right = CountTrees(num - root);
// number of possible trees with this root == left*right
sum += left * right;
}
return sum;
}
}
/** OUTPUT **/
No. of tree possible from :
0 nodes = 1
1 nodes = 1
2 nodes = 2
3 nodes = 5
4 nodes = 14
5 nodes = 42
6 nodes = 132
7 nodes = 429
8 nodes = 1430
9 nodes = 4862
The max number of binary trees that can be formed from n nodes is given by the Catlan Number C(n).
C(n) = (2n)! / (n+1)!*n! for n>=0.
Hi,
This is a pretty simple answer catalan number, but the questions asked is to write a program and when you write a program, the program dies after 30 or 35. So we use memoization in the code to improve it to run for a greater N.
After the memoization solution, the interviewer also asks if there is another way , then we go with DP as well.. I have documented all these into an article , hope this helps others techieme.in/techieme/count-binary-search-trees/
In case of Binary Trees- number of different non-isomorphic structures: (2^n - n ), n is number of nodes
In case of Binary Search Trees- number of different non-isomorphic structures = Catalan Numbers
isomorphic structures are those where ordering ( left/right matters ) ( refer geeksforgeeks)
Catalan Number...
- tridgell August 24, 2009