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 <[email protected]> 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 [email protected]. > 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 [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
