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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
