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 < bagana.bharatku...@gmail.com> 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 <monugoya...@gmail.com>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 <monish.gup...@gmail.com>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 <pawanjalsa.t...@gmail.com> 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 algogeeks@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. >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@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. >> > > > > -- > > **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* > <bagana.bharatku...@gmail.com> > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
