## 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