count total trees

Go down

count total trees

Post  Admin on Sat Aug 30, 2008 11:00 am

Write a program to count the total no. of binary trees possible with n nodes.
Try to optimise the solution.

Admin
Admin

Posts : 39
Join date : 2008-08-03

View user profile http://computerclub09mnnit.forumotion.net

Back to top Go down

Re: count total trees

Post  shivang on Sat Aug 30, 2008 1:12 pm

the total number of different binary trees that can be formed with n nodes can be given by CATALAN NUMBER
if b(n) denotes the no of different trees of n nodes than

b(n) = (2n)! / ( (n)!(n+1)! )
avatar
shivang

Posts : 22
Join date : 2008-08-11
Age : 29
Location : Tondon 174

View user profile

Back to top Go down

Re: count total trees

Post  ankurgutpa on Sun Aug 31, 2008 11:18 am

elaboration please? cheers
avatar
ankurgutpa

Posts : 44
Join date : 2008-08-10
Age : 30
Location : Tandon 72

View user profile

Back to top Go down

@papa

Post  prani on Sun Sep 07, 2008 11:24 am

try googling
Catalan Numbers:
the number of binary search trees possibble with n nodes is same as
--number of path in an nxn matrix above the leading diagonal from start to end
--the number of ways n people in a circlecan shake hands so that no hands cross
etc..
CLRS me dekho..

prani

Posts : 15
Join date : 2008-08-12

View user profile

Back to top Go down

Re: count total trees

Post  Akash Kumar on Wed Sep 10, 2008 8:55 am

Hi there,

Good to see this forum active. great work final years. It s good to see you guys actively participating in this forum and better still is to see that you guys are interested in the mathematical appeal of algorithms.

BTW here is another catalan number problem...You have a stack. It has a stream of numbers 1,2,3........N as input in that order. At any stage the stack spits out an element which is then printed on the screen. Your task is NOT to find the number of N-lettered strings printable using the stack ,I answered that (as if it were needed)..

No, You have to tell why the catalan recurrence fits in this case. Its simple, but still I feel, you should attempt it.

Akash Kumar

Posts : 4
Join date : 2008-09-10

View user profile

Back to top Go down

@Akash Sir

Post  prani on Thu Sep 11, 2008 5:27 am

Question not clear...

prani

Posts : 15
Join date : 2008-08-12

View user profile

Back to top Go down

Clarifying the Question

Post  Akash Kumar on Fri Sep 12, 2008 8:27 am

Hello,

Yaar question hai -

You have a stack which to which we feed a stream of integers 1,2,3 .... N as input. At any time during the stream eating process the stack can choose to hold the stream off for a while and have the element (or elements) on its top popped. the element popped from the stack gets printed. It is given that your stack will consume every element and have it popped when it likes. Thus the stack will print a string of N-letters in some order. Clearly some strings are printable using the stack and some are unprintable.

This is a Catalan Number Problem and we know that the number of possible printable strings when you have N-letters equals a Catalan Number. I hope you guys know the Catalan Number recurrence. I want you to show how you can arrive at that recurrence in this problem. Sure, you can throw in an analogy with some other Catalan Number problem - but spare it. I would like you to establish this recurrence for this particular case.

Hope this makes the problem more clear (or did it confuse the matters more Smile - if so tell me - I would then let you know whatever the hell i meant to say)

Akash Kumar

Posts : 4
Join date : 2008-09-10

View user profile

Back to top Go down

@Akash Sir..

Post  prani on Fri Sep 12, 2008 12:01 pm

For the n numbers in the stack..
Let Cn be the total number of strings
Now if we pop i elements from the string,The problem brakes down to two sub problem of length
Ci,Cn-i.
So ,Cn=Summations of(Ci*Cn-i) i from 1 to n
which is the popular Catalan number recurrence

prani

Posts : 15
Join date : 2008-08-12

View user profile

Back to top Go down

Re: count total trees

Post  Akash Kumar on Sat Sep 13, 2008 11:53 am

Yeah you are right...

But there is a scope for clarifying your answer better still... You see, the letter which gets printed at the end is a special character in the sense that you need to have an empty stack before this element makes its grand entry into the stack...

Thus, you obtain the recurrence saying Number of printable sequences = sum of Ci*Cn-i-1 where i goes from 1 to N....

It is actually this point I wanted to stress...Thats where the problem has a subtle jump. If you say that pushing and then popping i numbers first contributes Ci and then pushing remaining n-i elements and popping them contributes Cn-i - well thats were most of us make a mistake....

Think this way - I can have i elements pushed and all popped and then a set of j elements all pushed and popped followed by which remaining n-(j+i) are pushed and all popped - this will not support the Catalan recurrence!

Thats because you did not define the recurrence right.. To define it the right way, you need to make a comment about the last element the stack prints..

Give it a little more thought if you like...This problem requires nothing but a careful definition of recurrence and thats why I asked it....Just be careful when you define a recurrence..

Hope u understand it
-Akash

Akash Kumar

Posts : 4
Join date : 2008-09-10

View user profile

Back to top Go down

Re: count total trees

Post  Sponsored content


Sponsored content


Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum