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