count total trees
5 posters
Page 1 of 1
count total trees
Write a program to count the total no. of binary trees possible with n nodes.
Try to optimise the solution.
Try to optimise the solution.
Re: count total trees
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)! )
if b(n) denotes the no of different trees of n nodes than
b(n) = (2n)! / ( (n)!(n+1)! )
shivang- Posts : 22
Join date : 2008-08-11
Age : 35
Location : Tondon 174
Re: count total trees
elaboration please?
ankurgutpa- Posts : 44
Join date : 2008-08-10
Age : 36
Location : Tandon 72
@papa
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..
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
Re: count total trees
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.
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
Clarifying the Question
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 - if so tell me - I would then let you know whatever the hell i meant to say)
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 - 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
@Akash Sir..
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
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
Re: count total trees
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
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
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum