Sorry code got reposted twice here is the correct one
void getLevelSum(node* root,int level,int &minL,int &maxR,int left[],int
right[]){
if(!root) return ;
minL = min(minL,level);
maxR = max(maxR,level);
getLevelSum(root->left,level-1,minL,maxR,left,right);
getLevelSum(root->right,level+1,minL,maxR,left,right);
if(level<0)
left[abs(level)] +=root->data;
else
right[level] +=root->data;
}
On Sun, Oct 16, 2011 at 4:23 PM, Ankur Garg <[email protected]> wrote:
> I am assuming we are allowed to use space ..With that i make 2 arrays 1 to
> store values from left side and other from right side .
>
> Here is the func
>
>
> void getLevelSum(node* root,int level,int &minL,int &maxR,int left[],int
> right[]){
> if(!root) return ;
> minL = min(minL,level);
> maxR = max(maxR,level);
> getLevelSum(root->left,level-1,minL,maxR,left,right);
> getLevelSum(root->right,level+1,minL,maxR,left,right);
> if(level<0)
> left[abs(level)] +=root->data;
> else
> right[level] +=root->data;
> }
>
> I am traversing whole tree nodes only once but storing them in an array so
> Space complexity is also O(n) for me
>
> Anyone having a better solution or approach ?
>
>
> On Sun, Oct 16, 2011 at 9:27 AM, SUMANTH M <[email protected]> wrote:
>
>> Hi,
>>
>> A binary tree is given we need to print vertical sums of nodes. for
>> example
>>
>> 1 2 3 4 5
>>
>> | | 5 | |
>> | | / | \ | |
>> | | / | 8 |
>> | | / | / | \|
>> | 4 | / | 10
>> | / | \ 9 | |
>> | / | \ | |
>> 7 | 6 |
>> | | | | |
>> | | | | |
>> -----------------------------------------------
>> 7 4 20 8 10
>>
>> Here we need to print sum 7,4,20,8,10.
>>
>> -Thanks
>>
>> --
>> 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.
