@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 <shashank7andr...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.