CareerCup

create an array sum[] for storing the content.. initialised to 0
find the maximum depth of the tree...
make an inital call to fun(root,depth)
function fun is :

void fun (node *root, node level){
     sum[level]+=root->data;
       fun(root->left,level--);
       fun(root->right,level++);
}

takes O(n) complexity ..

i think level-- and level++ should be replaced with level-1 and level+1, respectively.

@Anonymous
This is a standard question. Google for vertical sum of a tree

i think level-- and level++ should be replaced with level-1 and level+1, respectively.

I agree with explorer.. :-P

I agree with explorer.. :-P

I agree with explorer.. :-P

If we take an array to store the vertical sums, it will be very difficult to decide the length of the array and the starting position of the root. I would take a doubly linked list to store the vertical sums and add nodes to left and right if required.

// Total array size should be 2 ^ Depth + 1
// Initialize the array with 0
//Call fun (head, size/2)

int[] sum = new int[size];
void Fun(Node head, int index)
{
Fun(head.Left, index -1);
sum[index] = head.Data;
Fun(head.Right, index + 1);
}

void verticalSum( struct tree * root, int a[], int pivot)
{
if(root== NULL)
return;

a[pivot]= a[pivot] + root->data;

if( root->left)
{ pivot--;
verticalSum(root->left,a,pivot);
}
if( root->right)
{ pivot++;
verticalSum(root->right,a,pivot);
}

}
int main()
{
int a[100];
for(i= 0; i < 100; i++)
a[i] = 0;

vericalSum( root, a, 10);


}

My solution with a deque ....

deque<int> dq;
int cursor = -1; /* cursor is the index of current node in deque */

void GetVerticalSum( Node *root )
{
if ( root == NULL )
return ;

if ( cursor == -1 ) /* reach left , add elem in deque head */
{
dq.push_front ( root->data );
cursor = 0;
}
else if ( cursor == dq.size() ) /* reach right, add elem in deque tail */
dq.push_back( root->data );
else /* No need to add new elem in deque */
dq[ cursor ] += root->data ;


/* traversal */
if ( root->left )
{
cursor--;
GetVerticalSum( root->left );
cursor++;
}
if ( root->right )
{
cursor++;
GetVerticalSum( root->right );
cursor--;
}
}

can u explain how ur sum Array is constrcuted for the given tree. Question is not clear.