Calculate vertical sum of a Binary Tree.

Solution #1: Vertical sums of a binary tree are the sum of its each vertical column. For e.g. consider the below tree,

                 5

             /        \

          3           8

         /  \        /    \

       2     4    6     9

Vertical Sum for first column: 2

Vertical Sum for second column: 3

Vertical Sum for third column: 15 (5+4+6)

Vertical Sum for fourth column: 8

Vertical Sum for fifth column: 9

Output: 2 3 15 8 9

Algorithm:

- start from root and hash its value in a map using a key, say, 'key_col'

- recursively hash left and right children with key value 'key_col-1' and 'key_col+1'

- if the key entry is not present in the hash map then create one and set value as 'root->data'

- if the key entry is already present then just add 'root->data' to the existing value

In the end, we have vertical sum stored in the hash map. Here is the code,

void mapNode(struct node* root, map& m, int col)
{
    if(root == NULL)
        return;
    
    map::iterator it = m.find(col);

    //if column is already mapped and map already
    //has some value stored for the column then
    //add root->data to already stored value, otherwise,
    //just store root->data.
    if(it == m.end())
        m.insert(pair(col, root->data));
    else
        it->second += root->data;

    mapNode(root->left, m, col-1);
    mapNode(root->right, m, col+1);
}

int main()
{
    struct node *root=NULL;
    map m;
    map::iterator iter;

    insert(&root, 50);
    insert(&root, 25);
    insert(&root, 100);
    insert(&root, 30);
    insert(&root, 20);
    insert(&root, 75);

    mapNode(root, m, 0);

    for(iter = m.begin(); iter != m.end(); iter++)
        printf("%d ", iter->second);

    printf("\n");

    return 0;
}