Vertical Sum of a Binary Tree

Problem Statement:
We have given a Binary tree, and we have to find the vertical sum of all the nodes that are in the same vertical line. And then, we have to print all sums through different vertical lines starting from the left-most vertical line to the right-most vertical line.

How to solve this problem?

Finding the vertical sum of a binary tree is a very interesting problem that involves calculating the sum of nodes along each vertical column in the tree. 

To find the solution of this program to get the vertical sum of a binary tree, we have to first understand the requirements of this question. So,

1. First, we have given a binary tree and each node of that tree has at most two child nodes.
2. Next, we have to calculate the vertical sum of a binary tree that falls in the same vertical column.

For example, In the above figure (Input 1),
The tree has 5 vertical lines,
Vertical line 1, has only one node 4. So, the sum of the first vertical line will be 4.
In Vertical line 2, again it has only one node 2. So, the sum of the second vertical line will be 2.
In vertical line 3, we have 3 nodes that lie in the same vertical line, those nodes are 1, 5 and 6, so the sum of the third vertical line is 12.
In vertical line 4, we have a separate node 3, the sum of the fourth line will be 3.
Finally, In the last vertical line 5, we have a node 7, so the sum of the fifth vertical line will be 7.

So, here we have to draw a vertical line and calculate the nodes together that lie in the same vertical line. And to solve this problem, we will use a depth-first traversal algorithm to calculate all the vertical sums of the binary tree.

So now read the full blog to know the solution to the “vertical sum of a binary tree” problem.

#include <iostream>
#include <map>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Function to perform a depth-first traversal and calculate vertical sums
void calculateVerticalSums(TreeNode* root, int column, std::map<int, int>& verticalSums) {
    if (root == nullptr) return;

    // Update the sum for the current vertical column
    verticalSums[column] += root->val;

    // Recursively calculate sums for left and right subtrees
    calculateVerticalSums(root->left, column - 1, verticalSums);
    calculateVerticalSums(root->right, column + 1, verticalSums);
}

// Function to find the vertical sum of a binary tree
std::map<int, int> verticalSum(TreeNode* root) {
    std::map<int, int> verticalSums;
    calculateVerticalSums(root, 0, verticalSums);
    return verticalSums;
}

// Helper function to create a binary tree (for demonstration purposes)
TreeNode* createBinaryTree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    return root;
}

// Helper function to display the vertical sum map
void displayVerticalSums(const std::map<int, int>& verticalSums) {
    for (const auto& pair : verticalSums) {
        std::cout << "Column " << pair.first << ": " << pair.second << std::endl;
    }
}

int main() {
    TreeNode* root = createBinaryTree();

    std::map<int, int> verticalSums = verticalSum(root);

    std::cout << "Vertical Sums:" << std::endl;
    displayVerticalSums(verticalSums);

    // Remember to deallocate memory to avoid memory leaks (not shown here for simplicity)

    return 0;
}

The output of the above code is:

Explanation of the code:

Now, let us understand the above code one by one:

1. First, we make the struct TreeNode to define the binary tree node. This structure has an integer value as val and two pointers as left and right.
2. Next, we will make calculateVerticalSums function which takes some parameters like TreeNode pointer as root, int column (to count column number), std::map& verticalSums for reference to the map to store the sums for each vertical column.
3. This above function will use a depth-first traversal algorithm and calculate the vertical sums one by one.
4. In the above function, if (root == nullptr), then it will return null which means there is no node to process.
5. Then, it will move to the verticalSums[column] variable and perform an operation ( verticalSums[column] += root->val) to update the sum for the current vertical column by adding the value of the current node to the sum already present in the verticalSum map variable. Since std::map automatically initializes missing keys to 0, this operation will either add the value of the current node to an existing sum or create a new entry in the map with the current node’s value, if there is no node available.
6. Then, recursively it will call the calculateVerticalSums function again by passing root->left, column – 1, verticalSums as a parameter. It will decrement the column number by 1 to represent a left shift in the vertical column. And in the same way, it will call for the right subtree recursively but it will increments the column number by 1 to represent a right shift in the vertical column.
7. Then, we will make a std::map verticalSum(TreeNode* root) function to find the vertical sum of the binary tree. It will take the root of the binary tree as input and returns a std::map containing the vertical sums.
8. Next, we add nodes in our binary tree and with the help of the displayVerticalSums function, we will print all the vertical sums.

Summary

So, this problem “vertical sum of a binary tree” uses a depth-first traversal algorithm to calculate the vertical sums of a binary tree. It then displays the sums for each vertical column from left to right indexes. Also, this algorithm has a time complexity of O(N), where N is the number of nodes present in the binary tree.