You could do any order traversal to get the list of values. - O(n) Apply the kth order statistic (where k = numNodes/2) to get the value - O(n)
Adjust the median depending on whether numNode is odd or even On Sun, Mar 27, 2011 at 8:03 PM, Balaji Ramani <[email protected]> wrote: > Hi, > > This is one approach to it: > > 1) Go to the first node in inorder traversal. Let the pointer be LP. > (Push the intermediate nodes to Lstack while doing this ) > 2) Go to the last node in inorder traversal. Let the pointer be RP. > (Push the intermediate nodes to Rstack while doing this ) > > while(LP->data < RP->data){ > LP = inordersuccessor(LP,Lstack) > // gets inorder successor and modifies Lstack accordingly > RP = inorderpredecessor(RP,Rstack) > // gets inorder predecessor and modifies Rstack accordingly > Lprev = LP > Rprev = RP; > } > > if(LP->data = RP->data){ // even number of elements > retrun LP->data; > }else{ > return Lprev->data + Rprev->data / 2 > } > > Time: O(n) > Memory: 2 * O ( log n) average > > Thanks, > Balaji. > > On Sun, Mar 27, 2011 at 7:17 PM, bittu <[email protected]> wrote: >> >> @all >> >> wake up geeks >> >> >> Thanks >> Shashank >> >> -- >> 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. > -- 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.
