I think we can solve this problem by changing the right sub tree of the root
in to linked list in the following way. Here is an example
5
4 7
2 3 8 9
5
4 9
2 3 8
7
This gives us access to the lowest number and the highest number in the
tree. We can start with the left most child and first right child of the
root.
On 27 July 2010 07:06, Gene <[email protected]> wrote:
> Look up threaded tree in wikipedia.
>
> On Jul 26, 9:12 pm, Snoopy Me <[email protected]> wrote:
> > Hey could you please give a very brief on what is meant by threads in
> > bst?
> >
> > On Jul 27, 5:17 am, Gene <[email protected]> wrote:
> >
> >
> >
> > > 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 <[email protected]> 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 <[email protected]> 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 <[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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Thanks and Regards,
N. Ravikanth
--
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.
