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