Conver your BST to a doubly linked list by doing an inorder traversal. Now do the normal find sum procedure
Sorry but i have no idea about normal tree case. On Tue, Mar 5, 2013 at 9:08 PM, Dave <dave_and_da...@juno.com> wrote: > @Marti: I'm not quite sure if you mean that there are two problems, one > with a BST and the other with an ordinary tree, or if you mean that one of > the summands comes from a BST and the other comes from an ordinary tree. > > If both values come from a BST, do two simultaneous inorder traversals, > one forwards (from left to right), and the other backwards (from right to > left). If the sum of the two current elements is less than the value, > advance the forward traversal, while if the sum is greater than the value, > advance the backward traversal. Quit when equality is reached or when the > two traversals reach the same element. O(n) time and O(log n) space if the > BST is reasonably balanced, although the space can be as large as O(n) if > the BST is severly unbalanced (as in case it has degenerated into a linked > list). > > In order to do two simultaneous traversals, use two stacks to keep track > of the state, as recursion won't allow you to do them. > > Dave > > On Tuesday, March 5, 2013 1:54:30 AM UTC-6, marti wrote: > >> Given a value , print two nodes that sum to the value in a BST and normal >> tree.. time:O(n), space O(logn). >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
