@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.-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. > > -- > 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.
