@ Gene
Your solution seems great and most appropriate one.
Just need to create threads in BST first.What will be time complexity
for that?
On Jul 25, 11:08 pm, Gene <gene.ress...@gmail.com> wrote:
> 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 <dona.1...@gmail.com> 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
