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
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;
}
}