Check the blog http://ds-gyan.blogspot.com/2009/12/median-of-stream-of-numbers.html
You can form similar tree with node having count of left elements. On Mar 8, 5:45 pm, Rohit Saraf <[email protected]> wrote: > once u do that.. the solution is trivial :P > -Rohit > > On Mon, Mar 8, 2010 at 5:54 PM, Nikhil Agarwal > <[email protected]>wrote: > > > > > On Mon, Mar 8, 2010 at 5:04 PM, Rohit Saraf > > <[email protected]>wrote: > > >> can we assume that we have the sizes of subtree rooted at all nodes in our > >> datastructure.? > > > Yeah,that can be lead to 1 solution.well done. > > >> -Rohit > > >> On Mon, Mar 8, 2010 at 5:02 PM, sharad kumar > >> <[email protected]>wrote: > > >>> @gaurav :ur sol u mean like tk the mem loc for each node and make it as > >>> array ? > > >>> On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta <[email protected] > >>> > wrote: > > >>>> Median of BST means : median of Sorted array of elements? is it? > > >>>> Convert BST into Hight Balance Search Tree then root node will be your > >>>> median. > > >>>> On Sun, Mar 7, 2010 at 2:42 AM, Nik_nitdgp > >>>> <[email protected]>wrote: > > >>>>> Given a BST (Binary search Tree) how will you find median in that? > >>>>> Constraints: > >>>>> -No extra memory. > >>>>> Algorithm should be efficient in terms of complexity. > >>>>> Write a solid secure code for it. > > >>>>> No extra memory--u cannot use stacks to avoid recursion. > >>>>> No static,global--u cannot use recursion and keep track of the > >>>>> elements visited so far in inorder. > > >>>>> -- > >>>>> 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. > > >>>> -- > >>>> 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. > > >>> -- > >>> 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. > > >> -- > >> 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 & Regards > > Nikhil Agarwal > > Junior Undergraduate > > Computer Science & Engineering, > > National Institute Of Technology, Durgapur,India > >http://tech-nikk.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. -- 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.
