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 <[email protected]> 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 <[email protected]> wrote: > > Dave, > > > > Can you provide the psuedo code for this.. > > > > Thanks, > > Swathi > > > > > > > > On Mon, Jun 27, 2011 at 7:30 PM, Dave <[email protected]> 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 <[email protected]> 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 <[email protected]> > 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 <[email protected]> > 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 <[email protected]> wrote: > > > > > > > > > -- > > > > > > > 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.-Hidequoted 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 [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. > > > > > > -- > > > > 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 [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.- 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 [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. > > -- 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.
