You'd know how to do this if you had a sorted array A, right? Start a
pointer at each end. Call the L and R.
L = 0;
R = length(A) - 1
while (L < R) {
while (L < R && A[L] + A[R} > k) --R;
if (A[L] + A[R} == k) return <L, R>;
++L;
}
return <failed>
Since you have a BST, just replace L and R with iterators that scan
from left to right and right to left through the tree. The ammortized
cost of an iterator call is O(1), and there are clearly O(n) calls,
where n = lengh(A).
The iterators can each contain a O(log n) stack, but you seem willing
to ignore log n stack space. You could get rid of the stacks by
threading the tree.
On Jul 24, 12:03 am, Priyanka Chatterjee <[email protected]> wrote:
> Given a binary search tree of n nodes, find two nodes whose sum is equal to
> a given number k in O(n) time and constant space.
> (ignoring recursion stack space)
>
> I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
> help me out with O(n) time and O(1) space.
>
> --
> Thanks & Regards,
> Priyanka Chatterjee
> Final Year Undergraduate Student,
> Computer Science & Engineering,
> National Institute Of Technology,Durgapur
> Indiahttp://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
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.
