ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Get Vertical Sum of Binary Tree

prodevelopertutorial October 8, 2020

Problem Statement:

You are given a root node, you need to calculate the vertical sum of the tree.

Consider the image below
binary_tree

Vertical-Line-1: has only one node 7 => vertical sum is 7
Vertical-Line-2: has only one node 10 => vertical sum is 10
Vertical-Line-3: has three nodes: 16, 15,18 => vertical sum is 16 + 15 + 18= 49
Vertical-Line-4: has only one node 25 => vertical sum is 25
Vertical-Line-5: has only one node 30 => vertical sum is 30

So the output should be 7, 10, 49, 25, 30

Solution:

The solution is very easy.

We need to calculate the HD for each node, and add the node values whose horizontal distance is the same.

We need to inorder traversal.

Solution in C++

#include <iostream>
#include <map>
#include <vector>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


void get_vertical_sum(Node *node, int hd, map<int, int> &myMap) 
{ 
    if (node == NULL) 
        return; 
  
    get_vertical_sum(node->left, hd-1, myMap); 
  
    myMap[hd] += node->data; 
  
    get_vertical_sum(node->right, hd+1, myMap); 
} 

  
int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    map < int, int> myMap; 
    map < int, int> :: iterator it; 

    get_vertical_sum(root, 0, myMap);

    for (it = myMap.begin(); it != myMap.end(); ++it) 
    { 
        cout << it->first << ": "
             << it->second << endl; 
    } 

    return 0;  
}

Output:

-2: 7
-1: 10
0: 49
1: 25
2: 30
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io