Re: [algogeeks] Re: BST Problem
Perform inorder traversal and store in an array. low = 0, high = size-1 while(low=high) { if ( a[low] + a[high] sum) low++; else if (a[low] + a[high] sum) high--; else return a[high] and [low] } On Mon, Aug 23, 2010 at 9:29 AM, R.ARAVINDH aravindhr...@gmail.com wrote: @giri: can u post d correct answer?? -- 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. -- 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: BST Problem
I am not sure if I am repeating the answer: The problem will reduce to find the pair of elements which will sum up to a particular number. Then read the below article, http://www.rawkam.com/?p=345 On Mon, Aug 23, 2010 at 9:29 AM, R.ARAVINDH aravindhr...@gmail.com wrote: @giri: can u post d correct answer?? -- 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. -- 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: BST Problem
Avik, yes the answer is obvious but your code doesn't find that. that 2 pointer approach is the correct one. On Tue, Aug 10, 2010 at 12:07 AM, Avik Mitra tutai...@gmail.com wrote: @Sekin. Sort the elements (increasing order). This has already been mentioned. So, answer will be 1, 100. -- 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. -- 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: BST Problem
as a hint, convert the BST to a sorted array and take two pointers one pointing to the first number and the other pointing to the last. Then, move pointers appropriately to find the two numbers summing up to k. complexity: O(n) 2010/8/5 Seçkin Can Şahin seckincansa...@gmail.com what about the case: array : 1 3 10 100 and k = 101. Your code doesn't find it I suppose. On Thu, Aug 5, 2010 at 11:15 PM, Avik Mitra tutai...@gmail.com wrote: Inorder traversal of the BST will give elements in sorted way. Let us assume that the sorted elements are in an array A of length N. set i=1; while i N-1 { if a[i] k, then output: No such node else if(a[i]==k) { if (a[i+1] ==0) output: Two nodes found BREAK; else output: No such node. BREAK. } else if(a[i] k ) { if(a[i]+a[i+1]==k) output: Two nodes found BREAK. else if(a[i]+a[i+1] k) output: No such node BREAK else if(a[i] +a[i+1] k) i++ ; } }//End of while-loop. -- 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. -- 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: BST Problem
the solution elegant..but is there any on the fly method by just exploiting the BST propertyby using left and right pointers -- 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: BST Problem
Two inorders would achieve the same thing without using an array. One pointer running inorder with LDR and other pointer running inorder with RDL. Compare the sum at the two nodes and then adjust them accordingly. On Fri, Aug 6, 2010 at 2:11 PM, Manjunath Manohar manjunath.n...@gmail.comwrote: the solution elegant..but is there any on the fly method by just exploiting the BST propertyby using left and right pointers -- 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. -- 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: BST Problem
do the inorder traversal of the bst ...this gives the sorted array.. from that use int i=0,j=length(array) while(ij) { if(array[i]+array[j]sum) --j; else if(array[i]+array[j]sum) ++i; else if((array[i]+array[j])==sum) return i,j else ++i,--j; } On Fri, Aug 6, 2010 at 3:10 PM, Chonku cho...@gmail.com wrote: Two inorders would achieve the same thing without using an array. One pointer running inorder with LDR and other pointer running inorder with RDL. Compare the sum at the two nodes and then adjust them accordingly. On Fri, Aug 6, 2010 at 2:11 PM, Manjunath Manohar manjunath.n...@gmail.com wrote: the solution elegant..but is there any on the fly method by just exploiting the BST propertyby using left and right pointers -- 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. -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST Problem
Chonku, you can do that only when you have the links to parent nodes. I couldn't come up with a way of doing what you said on a basic BST(nodes having pointers only to their 2 children) that is why I suggested using an array. It doesn't change the overall complexity but if you have an idea about how implement your idea on a basic BST, I would like to hear it. Thanks, Seckin On Fri, Aug 6, 2010 at 2:56 AM, sharad kumar aryansmit3...@gmail.comwrote: do the inorder traversal of the bst ...this gives the sorted array.. from that use int i=0,j=length(array) while(ij) { if(array[i]+array[j]sum) --j; else if(array[i]+array[j]sum) ++i; else if((array[i]+array[j])==sum) return i,j else ++i,--j; } On Fri, Aug 6, 2010 at 3:10 PM, Chonku cho...@gmail.com wrote: Two inorders would achieve the same thing without using an array. One pointer running inorder with LDR and other pointer running inorder with RDL. Compare the sum at the two nodes and then adjust them accordingly. On Fri, Aug 6, 2010 at 2:11 PM, Manjunath Manohar manjunath.n...@gmail.com wrote: the solution elegant..but is there any on the fly method by just exploiting the BST propertyby using left and right pointers -- 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. -- 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. -- 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.