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 &minL,int &maxR,int level){
if(!root) return ;
minL = min(minL,level);
maxR = max(maxR,level);
getLevelSum(root->left,minL,maxR,level-1);
getLevelSum(root->right,minL,maxR,level+1);
}
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.
