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
<rbalaji.psgt...@gmail.com> 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 <shashank7andr...@gmail.com> 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 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.
>
--
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.
