Find verticals sum of binary tree

Given a binary tree with integer nodes in it, the aim is to find verticals sum. Let’s discuss this with the below example.

Verticals sum of binary tree.
Sum of nodes in the same vertical level.

As shown in the image above, each vertical level has an index, like {-2, -1, 0, 1, 2} in the above picture. The result should be the sum of all the nodes vertically in the same index.

This problem can be solved using a hash map, here the key is the index of the vertical level of the binary tree. We can solve this in recursion by passing level-1 to all its left node and level+1 for its right node.

Here, we maintain a key for each vertical of the binary tree and assign this vertical to an index value. While processing the tree, if we find an index in the hash map, we just simply need to add current nodes data in the hash map value associated with the index. Finally, the hash map contains all the sums of verticals. Below is the code snippet of the solution.

// Utility function to find vertical sum
void findVertSumUtil(
	struct Node *root,
	int level,
	unordered_map<int, int> &res)
{
	if (root == NULL)
		return;
	findVertSumUtil(root->left, level - 1, res);
	if (res.find(level) == res.end())
	{
		res[level] = root->data;
	}
	else
	{
		res[level] += root->data;
	}
	findVertSumUtil(root->right, level + 1, res);
}

Complexity of the above solution is O(n). The third parameter of the above solution is the resultant hash map, which contains the sum of the vertical of the binary tree. The full code of this solution can be as shown below.

// Output
Verticals Sum: 
8  19  24  16  5

Complexity: O(n)

This is how we find verticals sum of any binary tree. If you know any better solution please let our readers know by commenting here below. Happy learning!.