CareerCup

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

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

shldnt it be catalan numbers

2^n-n

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

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

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

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

here n=3 so ans is 5.

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

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

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.

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.

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

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*

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*