@Dave: Thanks for pointing that out . In that case , if tree is really big and we want to *save memory* : *Algorithm #1 :* 1) Convert tree to a linked list ( Right rotation or left rotation ) : O(n) 2) Quick Select Kth largest element : Worst case O(n^2) ( when tree was already a bst + if we chose pivot to be fist node of linked list everytime) 3) apply second phase of DSW algorithm to recreate the tree. O(n) Time : O(n^2) Space: O(1) Bonus : After fist call tree is perfectly balanced
If tree is small , we want to *save run time* : *Algorithm #2 :* 1) Traverse tree , store elements in array : O(n) 2) Quick Select Kth largest element : O(n) Time : O(n) Space : O(n) On Thu, Sep 8, 2011 at 8:58 AM, Dave <[email protected]> wrote: > @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. > > -- 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.
