We can do it in a recursive manner:
public int getRecursiveMedian(Node node)
{
int leftMedian = 0;
int rightMedian = 0;
if(node.getLeft() != null)
{
leftMedian = getRecursiveMedian(node.getLeft());
}
if(node.getRight() != null)
{
rightMedian = getRecursiveMedian(node.getRight());
}
return leftMedian + rightMedian + (node.getValue()/2);
}
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.
