@Himanshu: You apparently are assuming that the data is presented in a binary search tree, but the original problem stated that the data is presented in an unordered array. You need to account for the complexity of forming the bst and how much space it will take.
Dave On Sep 7, 7:20 pm, Himanshu Neema <[email protected]> wrote: > Do reverse inorder and count number of nodes visited, Kth visited node will > be Kth largest. > Time : O(n) > Space : O(1) > > On Mon, Sep 5, 2011 at 5:16 PM, bharatkumar bagana < > > > > [email protected]> wrote: > > @monish: > > u'rs is correct , time =O(nlogn) Ok but, the constant behind this prog is > > very huge .. > > for every number coming in , u maintain minheap and maxheap,and also if the > > sizes are of mismatch , u delete from minheap and add that to max heap--- > > here deletion--O(logn),addition--O(logn),this occurs on an average for > > every 3 elements ... > > > On Mon, Sep 5, 2011 at 2:08 AM, sachin goyal <[email protected]>wrote: > > >> @anup,@sukran ithink u both are right in case of binary search tree... > >> we can traverse and then easily find the value... > >> but in case of heap first we have to create the heap and accordingly apply > >> the algo the create min heap..... > >> it will be the complex program.... > >> so simple is bst just traverse by inorder and compare > >> if anyone has simple solution or any other case then plz tell..... > > >> On Sun, Sep 4, 2011 at 9:56 PM, monish001 <[email protected]>wrote: > > >>> ALGO: > >>> 1. For each element 1 to k: > >>> insert in into min-heap > >>> 2. for each element k+1 to n > >>> delete the root of min-heap and insert this item into the min- > >>> heap > >>> 3. Finally you have a min-heap of k largest numbers and the root is > >>> your answer > > >>> COMPLEXITY: O(n logn) > > >>> -Monish > > >>> On Sep 3, 3:03 pm, teja bala <[email protected]> wrote: > >>> > //Asked in MS please help me with the coding or Give an algorithm > > >>> > Write code to return the kth largest element in a tree ...>>> function > >>> > prototype is int fucnkth(node *root,int k) > > >>> -- > >>> 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. > > >> -- > >> 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. > > > -- > > > **Please do not print this e-mail until urgent requirement. Go Green!! > > Save Papers <=> Save Trees > > *BharatKumar Bagana* > > **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar> > > * > > Mobile +91 8056127652* > > <[email protected]> > > > -- > > 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.- Hide quoted text - > > - Show quoted text - -- 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.
