[algogeeks] Re: number of BST's
Number of BST with n keysf(n) = [ \sum_{ i=1 to n} f(i-1)* f(n- i) ] Root node can be any of n keys. if it is ith ney in ascending order, it has i-1 keys to left and n-i keys to right. Can any one explain how/Why is it equal to catalan number? -Thanks Bujji On Aug 1, 1:08 pm, Manjunath Manohar manjunath.n...@gmail.com wrote: int count(int node) { int sum=0;i,left,right; for(i=0;inode;i++) { left=count(node-1); right=count(node-i); sum+=left*right; } return(sum); }- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: number of BST's
the calatan number can be derived using the code given above.. plz confirm by using wiki.. try 2 find derivation of catalan number.. On Mon, Aug 2, 2010 at 11:34 AM, bujji jajalabu...@gmail.com wrote: Number of BST with n keysf(n) = [ \sum_{ i=1 to n} f(i-1)* f(n- i) ] Root node can be any of n keys. if it is ith ney in ascending order, it has i-1 keys to left and n-i keys to right. Can any one explain how/Why is it equal to catalan number? -Thanks Bujji On Aug 1, 1:08 pm, Manjunath Manohar manjunath.n...@gmail.com wrote: int count(int node) { int sum=0;i,left,right; for(i=0;inode;i++) { left=count(node-1); right=count(node-i); sum+=left*right; } return(sum); }- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards Ankur Aggarwal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: number of BST's
int count(int node) { int sum=0;i,left,right; for(i=0;inode;i++) { left=count(node-1); right=count(node-i); sum+=left*right; } return(sum); } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: number of BST's
int countTree(int num) { if(num = 1) return 1; int sum =0; for(i =1; inum; ++i) { left = countTree(i-1); right = countTree(num - i); sum += left*right; } return sum; } The code snippet is self explanatory. Let me know if any difficulty. On Jul 30, 11:28 am, Pramod Negi negi.1...@gmail.com wrote: Follow up on Catalon Nubmer... On Fri, Jul 30, 2010 at 10:44 AM, Amit Jaspal amitjaspal...@gmail.comwrote: n is clearly a number lets say 3 then BST's with 1,2,3 values as key are to be calculated On Fri, Jul 30, 2010 at 9:08 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: @AMIT: what does n represents? On Fri, Jul 30, 2010 at 5:46 AM, sharad kumar aryansmit3...@gmail.comwrote: @amit is it BST or binary tree??cos BST is unique rite???binary tree meas use catalan numbers 2nCn/(n+1)! On Thu, Jul 29, 2010 at 9:56 PM, amit amitjaspal...@gmail.com wrote: Given the numbers from 1 to n, write an algorithm to find how many distinct binary search trees can be formed.. eg n=4, no of distinct bst's are 14. ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT IIIT- Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: number of BST's
the number of unique binary trees which can be formed with n nodes is (2^n)-n -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: number of BST's
catalan number works fine On Sat, Jul 31, 2010 at 4:55 PM, Soumya_Prasad_Ukil ukil.sou...@gmail.comwrote: @above, result is incorrect for n=4. It should print 14. On 31 July 2010 16:44, Manjunath Manohar manjunath.n...@gmail.com wrote: the number of unique binary trees which can be formed with n nodes is (2^n)-n -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, soumya prasad ukil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.