# Vertical Sum in Binary Tree

Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines.

**Examples:**

```
      1
    /   \
  2      3
 / \    / \
4   5  6   7
```

The tree has 5 vertical lines

Vertical-Line-1 has only one node 4 => vertical sum is 4\
Vertical-Line-2: has only one node 2=> vertical sum is 2\
Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12\
Vertical-Line-4: has only one node 3 => vertical sum is 3\
Vertical-Line-5: has only one node 7 => vertical sum is 7

So expected output is 4, 2, 12, 3 and 7

```java
class Solution {
    static class Pair {
        TreeNode root;
        int level;

        Pair(TreeNode node, int level) {
            this.root = node;
            this.level = level;
        }
    }

    public List<Integer> verticalTraversal(TreeNode root) {
        // Map for storing level -> List
        HashMap<Integer, Integer> map = new HashMap<>();
        int minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
        // Going for level order BFS
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(root, 0));
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                Pair node = q.poll();
                minLevel = Math.min(minLevel, node.level);
                maxLevel = Math.max(maxLevel, node.level);
                map.put(node.level, map.getOrDefault(node.level, 0) + node.root.val);
                if (node.root.left != null)
                    q.add(new Pair(node.root.left, node.level - 1));
                if (node.root.right != null)
                    q.add(new Pair(node.root.right, node.level + 1));
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = minLevel; i <= maxLevel; i++)
            ans.add(map.get(i));
        return ans;
    }
}
```
