You don't thread the tree when you're ready to search it. Rather you
maintain the threads as it's built, which adds nothing to the
asymptotic run time. Parent pointers are a simpler way to get the
same result. However, both solutions require O(n) extra memory for
tag bits or pointers. You're better off just using iterators with
O(log n) stacks. I don't think there's a way to solve this problem
in
O(n) time with less than O(log n) memory.
On Jul 26, 6:18 am, rahul patil <rahul.deshmukhpa...@gmail.com> wrote:
> @ 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.
