@Sagar: No. I didn't say that they were in parallel or that one was inside the other. Go back and read it again and you will see that I said that they were being performed simultaneously, with each one being advanced in certain circumstances, and that in order to do that you would have to use explicit stacks instead of recursion. Perhaps, instead, you misread or misunderstood it.
Dave On Jul 16, 12:24 pm, sagar pareek <sagarpar...@gmail.com> 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 <dave_and_da...@juno.com> 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 <sagarpar...@gmail.com> 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 <dave_and_da...@juno.com> 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 <ase.as...@gmail.com> 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 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. > > > > -- > > > **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 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. > > -- > **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 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.
