Infosys Interview Question 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).

- PP on August 09, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anonymous on August 09, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Lokendra Kumar Singh on August 09, 2007 | Flag
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

- AamzillaA on September 29, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- seeker on February 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

shldnt it be catalan numbers

- Anonymous on August 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ds is wrong

- anirudh on January 08, 2012 | Flag
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

- shruthi on September 24, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ritesh kumar singh on February 09, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- yogendra on February 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- harshsingla450 on February 12, 2011 | Flag
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.

- ritesh kumar singh on February 09, 2010 | Flag Reply
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

- srinivas on February 25, 2010 | Flag Reply
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.

- PraSin on April 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- csegau on May 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anand on August 18, 2011 | Flag
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.
answer is 5

- Anonymous on November 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

chup be chtuye

- Anonymous on June 25, 2012 | Flag
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...

- csehrs on February 12, 2011 | Flag Reply
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.

- Anonymous on April 29, 2011 | Flag Reply
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.

- jitu on May 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ritu on December 26, 2012 | Flag Reply
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*

- Anonymous on October 16, 2014 | Flag Reply
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*

- Anonymous on October 16, 2014 | Flag Reply


Add a Comment
Name:

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

Books

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

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More