@Atul007: No need to destroy the BST. Perform two simultaneous inorder traversals of the BST, one from left to right (the usual direction) and one from right to left. At any stage you have selected two nodes. If the sum is less than the given number, advance the left-to-right traversal; If the sum is greater, advance the right-to-left traversal. Quit with success when the sum equals the given number or with failure when the two traversals have reached the same node. Dave
On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote: > convert BST to sorted DLL.. > now it is a double linked list , so we can find 2 number in O(n) time by > keeping 2 pointers(one at start and one at end) from sorted DLL. > now convert DLL to BST. > > On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar <[email protected]<javascript:> > > wrote: > MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is > equal to given number in O(n) time and O(1) space. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/oizd-5CSfuoJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
