what you are telling will be the median of link list. not the median of tree. but previous solution told by Gaurav Gupta fails because we don't have to use the extra memory and for getting height. and balancing we have to use recurssion. i think the question asked is correct or not.. Are u missing something...?
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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
