## Infosys Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
0
of 0 vote

For 'n' nodes, it'll be catalan number C(n).

Comment hidden because of low score. Click to expand.
0

i can't understand how does 'labeled' and 'unlabeled' nodes effect the solution to the problem.

Comment hidden because of low score. Click to expand.
0

labeling the nodes will increase the number of trees which can be formed, because the number of permutations will increase as the nodes are distinct on being labeled. the solution in case of labeled nodes is given by Quadruple factorial.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

this is the wrong answer the correct answer is only 1, because if u don't know which is the root or a child it is just one pattern, i.e. a single line connecting 3 vertices, no matter what shape u give to it.

for more info, search google books for : unlabelled trees.

Comment hidden because of low score. Click to expand.
0
of 0 vote

shldnt it be catalan numbers

Comment hidden because of low score. Click to expand.
0

ds is wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

2^n-n

2^3=8
8-3=5
so 5 is the answer

Comment hidden because of low score. Click to expand.
0

``bb shruti,if u don't know the formula then plz don't mislead anyone.``

Comment hidden because of low score. Click to expand.
0

shruti ,i think this not an answer..........

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0
of 0 vote

BB shruti,if u don't know the formula plz don't mislead anyone.

Comment hidden because of low score. Click to expand.
0
of 0 vote

sir, send me some interview point of questions to srinivasv123@ymail.com

Comment hidden because of low score. Click to expand.
0
of 0 vote

It is CATALAN NUMBER given by formula
(2n)!
---------,
(n+1)!n!

here n=3 so ans is 5.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Catalan number is correct solution for this problem. Visit this link for details mathworld.wolfram.com/CatalanNumber.html

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

chup be chtuye

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have invented the best formula to get the no of distinct binary trees for n no. of nodes(unlabelled i.e. no diff names are given to diff nodes)..

``n[bt]= n-2;``

where n[bt]= no. of distinct binary trees possible; n= no. of unlabelled nodes; 2 as a constant;

check it out friends...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

catalog no is not the answer here because for catalog no here n should be no of internal node ,not the total no of nodes.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

your explanatition is little bit confusing why you subtract one ..if you do so then then it will happen in all rest of 2 cases
so plzzz check it then give ans on internet plz don't waste time of others
btech 2nd yr cse student
gla university mathura
THE RANKED ONE UNIVERSITY OF INDIA*

Comment hidden because of low score. Click to expand.
0
of 0 vote

your explanatition is little bit confusing why you subtract one ..if you do so then then it will happen in all rest of 2 cases
so plzzz check it then give ans on internet plz don't waste time of others
btech 2nd yr cse student
gla university mathura
THE RANKED ONE UNIVERSITY OF INDIA*

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.