how about converting the BST into a doubly linked list...but this will definitely modify the BST..
On Mon, Jun 27, 2011 at 11:32 PM, Swathi <chukka.swa...@gmail.com> wrote: > Dave, > > I am unable to write code for this so i am asking your help. > > Thanks, > Swathi > > > On Mon, Jun 27, 2011 at 11:28 PM, Dave <dave_and_da...@juno.com> wrote: > >> @Swathi: No. I think the high level description should be adequate for >> you to write your own code or pseudocode, albeit recognizing that you >> may have to look up how to do an inorder traversal using a stack >> instead of recursion. >> >> Dave >> >> On Jun 27, 9:34 am, Swathi <chukka.swa...@gmail.com> wrote: >> > Dave, >> > >> > Can you provide the psuedo code for this.. >> > >> > Thanks, >> > Swathi >> > >> > >> > >> > On Mon, Jun 27, 2011 at 7:30 PM, Dave <dave_and_da...@juno.com> wrote: >> > > @Sunny. Mea culpa. You are correct. Revised (and correct) algorithm. >> > > Do two inorder traversals, one in the usual (descend to the left >> > > before descendung to the right) direction and the other in the >> > > reversed(descend to the right before descending to the left) >> > > direction. Let u and r be the current nodee of the two traversals, >> > > respectively. If u + r < x, then advance the usual traversal and >> > > repeat the comparison. If u + r > x, advance the reverse traversal and >> > > repeat the comparison. If u + r = x, and if u != r, then terminate >> > > with success. If u = r, then terminate with failure. >> > >> > > Dave >> > >> > > On Jun 27, 7:53 am, sunny agrawal <sunny816.i...@gmail.com> wrote: >> > > > @Dave >> > > > i think your solution won't work >> > > > consider inorder traversal of a BST is 1 6 7 8 15 and x = 14 >> > > > initially both u,v (1,1) >> > > > according to u your algorithm will proceed like >> > > > (1,1) -> (1,6) -> (1,7) -> (1,8) -> (1,15) -> (6,15) ............ -> >> > > (15,15) >> > >> > > > and clearly in second step of your solution if (u+v) > x after >> advancing >> > > u >> > > > still u+v will be greater than x >> > > > so something is wrong >> > > > I think your solution will work in case we need to find 2 nodes with >> > > > difference x. >> > >> > > > correct me if i am wrong.!! >> > >> > > > On Mon, Jun 27, 2011 at 6:13 PM, Dave <dave_and_da...@juno.com> >> wrote: >> > > > > @Nishant: No need to store the data in an array. Do two inorder >> > > > > traversals simultaneously. Let u and v be the current nodes of the >> two >> > > > > traversals, respectively. If u + v < x, then advance the "v" >> > > > > traversal. If u + v > x, advance the "u" traversal. >> > >> > > > > Dave >> > >> > > > > On Jun 27, 3:40 am, Nishant Mittal <mittal.nishan...@gmail.com> >> wrote: >> > > > > > do inorder traversal of tree and store values in an array. >> > > > > > Now find pairs by applying binary search on array.. >> > >> > > > > > On 6/27/11, manish kapur <manishkapur.n...@gmail.com> wrote: >> > >> > > > > > > -- >> > > > > > > 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.-Hidequotedtext - >> > >> > > > > > - 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 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. >> > >> > > > -- >> > > > Sunny Aggrawal >> > > > B-Tech IV year,CSI >> > > > Indian Institute Of Technology,Roorkee- 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 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.- 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 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. >> >> > -- > 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. > -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=100000655377926 * -- 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.
