@WgpShashank..
As pointed out by you, yes i agree that catalan no. has various
interpretations. But, keeping that in mind it doesn't mean that the
only relationship b/w binary tree and catalan no. is the following:
Catalan No = No. of full binary trees having (n+1) leaves..
If you read the question posted, it says that we need to find the no.
of binary trees whose inorder sequence adheres to the given sequence
of size N.
Say the nos. are a1, a2, a3, ....., aN
Now, given the above sequence, we need to find the no. of binary trees
which mimic the above sequence as its own inorder sequence..
As in my earlier post i have given out a recurrence relation for the
same:
-----------------------------
Say, F(n) denotes the no. of binary trees that can be formed using N
elements given the inorder sequence..
F(n) = SumOver(i= 1 to N) { F(i-1) * F(N-i) }
which is nothing but..
F(N) = (2n C n)/ (n+1) i.e. catalan's no.
------------------------------
Now, if you look at the recurrence its the same as Segner's recurrence
relation (which is basically catalan no)
Look at the following link: (Segner's recurrence relation)
http://en.wikipedia.org/wiki/Catalan_number#First_proof
On Jan 24, 4:15 pm, WgpShashank <[email protected]> wrote:
> @Lucifier . Hope u studied from Wiki Check
> ithttp://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinato...
>
> Correct me if i am missing something ?
>
> Thanks
> Shashank Mani
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
