and so it must not be O(n) On Sat, Jul 16, 2011 at 10:54 PM, sagar pareek <[email protected]>wrote:
> ok i got it.... > actually u written wrong that f/w and reverse traversal are running > parallel > u must wrote that f/w traversal inside reverse or vice versa > > On Sat, Jul 16, 2011 at 10:35 PM, Dave <[email protected]> wrote: > >> @Sagar: No problem. The algorithm would do only forward traversal >> steps until it got to root_>left, whereupon F + R = K. >> >> Dave >> >> On Jul 16, 11:40 am, sagar pareek <[email protected]> wrote: >> > @dave >> > what if the k= root->left + right most leaf ? >> > how ur algo works on it? >> > >> > >> > >> > >> > >> > On Sat, Jul 16, 2011 at 9:28 PM, Dave <[email protected]> wrote: >> > > @Noobcoder: To do it in O(n) without destroying the BST, do two >> > > inorder traversals simultaneously, one in the normal forward (left >> > > subtree first) direction and one in the reverse direction (right >> > > subtree first). Let the two current nodes have value F and R >> > > respectively. If F + R = K, return success. If F = R, return failure. >> > > If F + R < K, advance the forward traversal. Otherwise (F + R > K), >> > > advance the reverse traversal. To do the traversals simultaneously, >> > > you will have to use explicit stacks instead of recursion. >> > >> > > Dave >> > >> > > On Jul 16, 9:01 am, noobcoder <[email protected]> wrote: >> > > > Given a BST containing integers, and a value K. You have to find two >> > > > nodes that give sum = K. >> > >> > > -- >> > > 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. >> > >> > -- >> > **Regards >> > SAGAR PAREEK >> > COMPUTER SCIENCE AND ENGINEERING >> > NIT ALLAHABAD- 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. >> >> > > > -- > **Regards > SAGAR PAREEK > COMPUTER SCIENCE AND ENGINEERING > NIT ALLAHABAD > > -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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.
