Given a binary tree, calculate sum of all nodes for each diagonal having negative slope (\). Assume that the left and right child of a node makes 45 degree angle with the parent.
This problem can be easily solved with the help of hashing. The idea is to create an empty map where each key in the map represents a diagonal in the binary tree and its value maintains sum of all nodes present in the diagonal. Then we do a pre-order traversal of the tree and update the map. For each node, we recurse for its left subtree by increasing diagonal by 1 and recurse for right subtree with same diagonal.
// Data structure to store a Binary Tree node
Node *left, *right;
// Recursive function to do a pre-order traversal of the tree and
// fill the map with diagonal sum of elements
void diagonalSum(Node* root, int diagonal, auto &map)
// base case: empty tree
if (root == nullptr)
// update the current diagonal with node's value
map[diagonal] += root->data;
// recurse for left subtree by increasing diagonal by 1
diagonalSum(root->left, diagonal + 1, map);
// recurse for right subtree with same diagonal
diagonalSum(root->right, diagonal, map);
// Function to print the diagonal sum of given binary tree
void diagonalSum(Node* root)
// create an empty map to store diagonal sum for every slope
map<int, int> map;
// do pre-order traversal of the tree and fill the map
diagonalSum(root, 0, map);
// traverse the map and print diagonal sum
for (auto it: map)
cout << it.second << " ";
The time complexity of above solution is O(nlog(n)) and auxiliary space used by the program is O(n).
2. Modify the solution to print diagonal sum for diagonals having positive slope (/).
Thanks for reading.