@Sagar: The algorithm visits each node at most 3 times: Once when descending from its parent, once when ascending from its left child, and once when ascending from its right child. Furthermore, one node is eliminated from contention with every three comparisons of F with R. Thus, there are no more than 3n traversal steps and no more than 3n comparisons.Thus, it is O(n).
Dave On Jul 16, 12:34 pm, sagar pareek <sagarpar...@gmail.com> wrote: > and so it must not be O(n) > > On Sat, Jul 16, 2011 at 10:54 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 > > -- > **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.
