Infosys Interview Question
Software Engineer / Developersi can't understand how does 'labeled' and 'unlabeled' nodes effect the solution to the problem.
GATE 2007 CS , Question 12
Q. The maximum number of binary trees that can be formed with three
unlabeled nodes.
A)1 B)5 C)4 D) 3
ANS:
A binary tree can have utmost 2 nodes.
I wish I could have drawn the tree to make explanations simple. But
drawing is taking a lot of time, so please forgive me the lack of
visual info and try to get the picture.
While placing a new node , two conditions should be met.
1. It should be connected to a previously placed node , unless its the
first node , ie root
2. It should be placed in a valid position, ie as a right child or
left child of an existing node , if its not the first node.
When we add a node to a binary tree, each newly added node consumes
one previously existing valid position and adds two new valid
positions. There fore net addition in no of valid positions after
connecting a new node to a binary tree is 2-1=1.
In a more general case, if it was an n-ary tree, each new node will
consume one previously existing valid position for adding a new node
and adds n new valid positions to the n-ary tree. So the net addition
of valid positions in an n-ary tree after adding a new node will be
n-1.
Another point is that , if a binary tree has k nodes the number of
valid positions to add a new node that the resulting tree is still a
binary tree will be always k+1.
Now with this concept lets approach the problem ,
With one unlabeled node, there is only one way to create a binary tree.
With 2 unlabeled nodes, we can create 2 binary trees by connecting the
second node either as a left child or right child of root.
With 2 nodes , the number of valid positions we have to create a three
nodes binary tree is 3.
But there are two ways in which we can create a 2 node binary three .
Therefore total options we have to create a 3-node binary tree is 2*3
= 6. But among these 6 trees two are symmetric, and since the nodes
are unlabelled we have to consider them as a single tree. There fore
the total number of binary trees possible with 3 unlabelled nodes is
6-1 =5.
There fore answer is B
Can some one tell how many identical trees (same shape) will be there
in a binary tree if there are n-labeled nodes. If n is even there will
be no identical trees. But if n is odd, i think there will be (n-1)/2
identical trees. Can someone please give me a proof for this ? I
simply drew all the trees and counted them.
In the above problem if there were n unlabelled trees the maximum
number of binary trees possible will be what ?
Thanks and regards,
AamzillaA
@shruti ur formula is gud 1 but it is valid if u are allowed to use any no of nodes (within the given no) to make a tree
i.e. if n=3 then u cn use n=0,1,2,3 to make a bt....bt i if this ques is saying that u hv 3 nodes and u hv to mk distinct trees out of it, then u cant use this formula..then the formula is that given by "csehrs" in the last.. go 4 it
hey ur formula to find the number of trees is wrong
please check, when number of node=4 it should be 12 but by ur way it comes out to be 14...
correct if i am wrong
oye CATALAN. try thinking from basics. Who the hell would remember ur catalan stuff in the interview.
Moreover it will give a impression of u as a maggu and not a good thinker.
answer is 5
Basically Its only with the help of catalan number you can find the total no of different binary trees for unlabelled vertices.
For labelled vertices a formula given by Arthur cayley the discoverer of trees was n^(n-2)
For further refrences check with the references book of graph theory you can check it out over there easily.
And the formula above given for the catalan number is correct.
and its come out to be 14 only you are missing some arrangements try it out you will come to know anout it.
For 'n' nodes, it'll be catalan number C(n).
- PP August 09, 2007