Question:
Given a binary tree root node, get the level wise sum.
Example:
Consider the image given below
Level 1 Sum = 16
Level 2 Sum = 10 + 25 = 35
Level 3 Sum = 7 + 15 + 18 + 30 = 70
Solution:
While doing level order traversal, compute the sum at each level and print it to output.
Solution on C++
#include <iostream> #include <queue> #include <stack> 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; } }; int get_level_sum( Node *root) { if (root == NULL) return 0; queue<Node*> q; q.push(root); while (!q.empty()) { int count = q.size() ; int level_sum = 0; while (count--) { Node *temp = q.front(); q.pop(); level_sum = level_sum + temp->data; if (temp->left != NULL) q.push(temp->left); if (temp->right != NULL) q.push(temp->right); } cout<<"Level sum = "<<level_sum<<endl; } return 0; } 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); get_level_sum(root); return 0; }
Output:
Level sum = 16 Level sum = 35 Level sum = 70