Get Vertical Sum of Binary Tree

Problem Statement:

You are given a root node, you need to calculate the vertical sum of the tree.

Consider the image below

Vertical-Line-1: has only one node 7 => vertical sum is 7
Vertical-Line-2: has only one node 10 => vertical sum is 10
Vertical-Line-3: has three nodes: 16, 15,18 => vertical sum is 16 + 15 + 18= 49
Vertical-Line-4: has only one node 25 => vertical sum is 25
Vertical-Line-5: has only one node 30 => vertical sum is 30

So the output should be 7, 10, 49, 25, 30

Solution:

The solution is very easy.

We need to calculate the HD for each node, and add the node values whose horizontal distance is the same.

We need to inorder traversal.

Solution in C++

#include <iostream>
#include <map>
#include <vector>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


void get_vertical_sum(Node *node, int hd, map<int, int> &myMap) 
{ 
    if (node == NULL) 
        return; 
  
    get_vertical_sum(node->left, hd-1, myMap); 
  
    myMap[hd] += node->data; 
  
    get_vertical_sum(node->right, hd+1, myMap); 
} 

  
int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    map < int, int> myMap; 
    map < int, int> :: iterator it; 

    get_vertical_sum(root, 0, myMap);

    for (it = myMap.begin(); it != myMap.end(); ++it) 
    { 
        cout << it->first << ": "
             << it->second << endl; 
    } 

    return 0;  
}  

Output:

-2: 7
-1: 10
0: 49
1: 25
2: 30