Given a Generic Tree consisting of N nodes (rooted at 0) where each node is associated with a value, the task for each level of the Tree is to find the sum of all node values present at that level of the tree.
Examples:
Input: node_number = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }, node_values = { 2, 3, 4, 4, 7, 6, 2, 3, 9, 1 }
Output:
Sum of level 0 = 2
Sum of level 1 = 7
Sum of level 2 = 14
Sum of level 3 = 18
Explanation :
- Nodes on level 0 = {1} with value is 2
- Nodes on level 1 = {2, 3} and their respective values are {3, 4}. Sum = 7.
- Nodes on level 2 = {4, 5, 8} with values {4, 7, 3} respectively. Sum = 14.
- Nodes on level 3 = {6, 7, 9, 10} with values {6, 2, 9, 1} respectively. Sum = 18
Input: node_number = { 1 }, node_values = { 10 }
Output: Sum of level 0 = 10
Approach: Follow the steps below to solve the problem:
- Traverse the tree using DFS or BFS
- Store the level of this node using this approach.
- Then, add the node values to the corresponding level of the node in an array, say sum[ ].
- Print the array sum[] showing the sum of all nodes on each level.
Below is the implementation of the above approach :
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>using namespace std;// Function to add edges to the treevoid add_edge(int a, int b, vector<vector<int> >& tree){ // 0-based indexing a--, b--; tree[a].push_back(b); tree[b].push_back(a);}// Function to print sum of// nodes on all levels of a treevoid dfs(int u, int level, int par, int node_values[], vector<vector<int> >& tree, map<int, int>& sum, int& depth){ // update max depth of tree depth = max(depth, level); // Add value of current node // to its corresponding level sum[level] += node_values[u]; for (int child : tree[u]) { if (child == par) continue; // Recursive traverse child nodes dfs(child, level + 1, u, node_values, tree, sum, depth); }}// Function to calculate sum of// nodes of each level of the Treevoid getSum(int node_values[], vector<vector<int> >& tree){ // Depth of the tree int depth = 0; // Stores sum at each level map<int, int> sum; dfs(0, 0, -1, node_values, tree, sum, depth); // Print final sum for (int i = 0; i <= depth; i++) { cout << "Sum of level " << i << " = " << sum[i] << endl; }}// Driver Codeint32_t main(){ // Create a tree structure int N = 10; vector<vector<int> > tree(N); add_edge(1, 2, tree); add_edge(1, 3, tree); add_edge(2, 4, tree); add_edge(3, 5, tree); add_edge(3, 8, tree); add_edge(5, 6, tree); add_edge(5, 7, tree); add_edge(8, 9, tree); add_edge(8, 10, tree); int node_values[] = { 2, 3, 4, 4, 7, 6, 2, 3, 9, 1 }; // Function call to get the sum // of nodes of different level getSum(node_values, tree); return 0;} |
Java
// Java implementation of// the above approachimport java.io.*;import java.util.*;class GFG{ static Map<Integer, Integer> sum = new HashMap<>();static int depth = 0;// Function to add edges to the treestatic void add_edge(int a, int b, ArrayList<ArrayList<Integer>> tree){ // 0-based indexing a--; b--; tree.get(a).add(b); tree.get(b).add(a);} // Function to print sum of// Nodes on all levels of a treestatic void dfs(int u, int level, int par, int []node_values, ArrayList<ArrayList<Integer>> tree){ // Update max depth of tree depth = Math.max(depth, level); // Add value of current node // to its corresponding level if (sum.containsKey(level)) { sum.put(level, sum.get(level) + node_values[u]); } else sum.put(level,node_values[u]); for(int child : tree.get(u)) { if (child == par) continue; // Recursive traverse child nodes dfs(child, level + 1, u, node_values, tree); }} // Function to calculate sum of// nodes of each level of the Treestatic void getSum(int []node_values, ArrayList<ArrayList<Integer>> tree){ dfs(0, 0, -1, node_values, tree); // Print final sum for(int i = 0; i <= depth; i++) { System.out.println("Sum of level " + (int) i + " = " + sum.get(i)); }} // Driver Codepublic static void main (String[] args) { // Create a tree structure int N = 10; ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < N; i++) tree.add(new ArrayList<Integer>()); add_edge(1, 2, tree); add_edge(1, 3, tree); add_edge(2, 4, tree); add_edge(3, 5, tree); add_edge(3, 8, tree); add_edge(5, 6, tree); add_edge(5, 7, tree); add_edge(8, 9, tree); add_edge(8, 10, tree); int []node_values = { 2, 3, 4, 4, 7, 6, 2, 3, 9, 1 }; // Function call to get the sum // of nodes of different level getSum(node_values, tree);}}// This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 implementation of# the above approach# Function to add edges to the treedef add_edge(a, b): global tree # 0-based indexing a, b = a - 1, b - 1 tree[a].append(b) tree[b].append(a)# Function to print sum of# nodes on all levels of a treedef dfs(u, level, par, node_values): global sum, tree, depth # update max depth of tree depth = max(depth, level) # Add value of current node # to its corresponding level sum[level] = sum.get(level, 0) + node_values[u] for child in tree[u]: if (child == par): continue # Recursive traverse child nodes dfs(child, level + 1, u, node_values)# Function to calculate sum of# nodes of each level of the Treedef getSum(node_values): global sum, depth, tree # Depth of the tree # depth = 0 # Stores sum at each level # map<int, int> sum dfs(0, 0, -1, node_values) # Prfinal sum for i in range(depth + 1): print("Sum of level", i, "=", sum[i])# Driver Codeif __name__ == '__main__': # Create a tree structure N = 10 tree = [[] for i in range(N+1)] sum = {} depth = 0 add_edge(1, 2) add_edge(1, 3) add_edge(2, 4) add_edge(3, 5) add_edge(3, 8) add_edge(5, 6) add_edge(5, 7) add_edge(8, 9) add_edge(8, 10) node_values = [2, 3, 4, 4, 7, 6, 2, 3, 9, 1] # Function call to get the sum # of nodes of different level getSum(node_values) # This code is contributed by mohit kumar 29. |
C#
// C# implementation of// the above approachusing System;using System.Collections.Generic;class GFG{ static Dictionary<int, int> sum = new Dictionary<int,int>(); static int depth = 0; // Function to add edges to the treestatic void add_edge(int a, int b, List<List<int>> tree){ // 0-based indexing a--; b--; tree[a].Add(b); tree[b].Add(a);}// Function to print sum of// Nodes on all levels of a treestatic void dfs(int u, int level, int par, int []node_values, List<List<int>> tree ){ // update max depth of tree depth = Math.Max(depth, level); // Add value of current node // to its corresponding level if(sum.ContainsKey(level)) sum[level] += node_values[u]; else sum[level] = node_values[u]; foreach (int child in tree[u]) { if (child == par) continue; // Recursive traverse child nodes dfs(child, level + 1, u, node_values, tree); }}// Function to calculate sum of// nodes of each level of the Treestatic void getSum(int []node_values, List<List<int>> tree){ dfs(0, 0, -1, node_values, tree); // Print final sum for (int i = 0; i <= depth; i++) { Console.WriteLine("Sum of level " + (int) i + " = "+ sum[i]); }}// Driver Codepublic static void Main(){ // Create a tree structure int N = 10; List<List<int> > tree = new List<List<int>>(); for(int i = 0; i < N; i++) tree.Add(new List<int>()); add_edge(1, 2, tree); add_edge(1, 3, tree); add_edge(2, 4, tree); add_edge(3, 5, tree); add_edge(3, 8, tree); add_edge(5, 6, tree); add_edge(5, 7, tree); add_edge(8, 9, tree); add_edge(8, 10, tree); int []node_values = {2, 3, 4, 4, 7,6, 2, 3, 9, 1}; // Function call to get the sum // of nodes of different level getSum(node_values, tree);}}// This code is contributed by bgangwar59. |
Javascript
<script>// Javascript implementation of// the above approachvar sum = new Map();var depth = 0; // Function to add edges to the treefunction add_edge(a, b, tree){ // 0-based indexing a--; b--; tree[a].push(b); tree[b].push(a);}// Function to print sum of// Nodes on all levels of a treefunction dfs(u, level, par, node_values, tree){ // Update max depth of tree depth = Math.max(depth, level); // Push value of current node // to its corresponding level if (sum.has(level)) sum.set(level, sum.get(level) + node_values[u]); else sum.set(level, node_values[u]) for(var child of tree[u]) { if (child == par) continue; // Recursive traverse child nodes dfs(child, level + 1, u, node_values, tree); }}// Function to calculate sum of// nodes of each level of the Treefunction getSum(node_values, tree){ dfs(0, 0, -1, node_values, tree); // Print final sum for(var i = 0; i <= depth; i++) { document.write("Sum of level " + i + " = "+ sum.get(i) + "<br>"); }}// Driver Code// Create a tree structurevar N = 10;var tree = [];for(var i = 0; i < N; i++) tree.push([]); add_edge(1, 2, tree);add_edge(1, 3, tree);add_edge(2, 4, tree);add_edge(3, 5, tree);add_edge(3, 8, tree);add_edge(5, 6, tree);add_edge(5, 7, tree);add_edge(8, 9, tree);add_edge(8, 10, tree);var node_values = [ 2, 3, 4, 4, 7,6, 2, 3, 9, 1 ];// Function call to get the sum// of nodes of different levelgetSum(node_values, tree);// This code is contributed by rrrtnx</script> |
Output
Sum of level 0 = 2 Sum of level 1 = 7 Sum of level 2 = 14 Sum of level 3 = 18
Time Complexity: O(N)
Auxiliary Space: O(N)
Iterative Approach(Level Order Traversal using Queue Data Structure):
Follow the below steps to solve the above problem:
1) Perform level Order Traversal and keep track of level and sum at each level.
2) At each level calculate sum and print sum along with level.
3) Repeat the step-2 at each level till last level.
Below is the implementation of above approach:
C++
// THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999)// C++ Implementation of above approach#include<bits/stdc++.h>using namespace std;// a binary tree nodestruct Node{ int data; Node *left, *right; Node(int data){ this->data = data; this->left = this->right = NULL; }};// a utility function to create a new nodeNode* newNode(int data){ return new Node(data);}void getSum(int node_values[], Node* root){ queue<Node*> q; q.push(root); int level = 0; while(!q.empty()){ int n = q.size(); int sum = 0; for(int i = 0; i<n; i++){ Node* front_node = q.front(); q.pop(); sum += node_values[front_node->data - 1]; if(front_node->left) q.push(front_node->left); if(front_node->right) q.push(front_node->right); } cout<<"Sum of level "<<level<<" : "<<sum<<endl; level++; }}// driver code to test above functionint main(){ Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->right->left = newNode(5); root->right->right = newNode(8); root->right->left->left = newNode(6); root->right->left->right = newNode(7); root->right->right->left = newNode(9); root->right->right->right = newNode(10); int node_values[] = {2,3,4,4,7,6,2,3,9,1}; // function call to get the sum // of nodes of different level getSum(node_values, root); return 0;} |
Java
import java.util.LinkedList;import java.util.Queue;class Node { int data; Node left, right; public Node(int data) { this.data = data; this.left = this.right = null; }}public class GFG { public static void getSum(int[] node_values, Node root) { // Create a queue to store the nodes of the binary // tree Queue<Node> q = new LinkedList<>(); // Add the root node to the queue q.add(root); // Initialize the level to 0 int level = 0; // Loop until the queue is empty while (!q.isEmpty()) { // Get the number of nodes at the current level int n = q.size(); // Initialize the sum to 0 int sum = 0; // Loop through all the nodes at the current // level for (int i = 0; i < n; i++) { // Get the front node from the queue Node front_node = q.poll(); // Add the value of the node to the sum sum += node_values[front_node.data - 1]; // Add the left child of the front node to // the queue if it exists if (front_node.left != null) { q.add(front_node.left); } // Add the right child of the front node to // the queue if it exists if (front_node.right != null) { q.add(front_node.right); } } // Print the sum of the nodes at the current // level System.out.println("Sum of level " + level + " : " + sum); // Increment the level level++; } } public static void main(String[] args) { // Create the binary tree Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.left = new Node(5); root.right.right = new Node(8); root.right.left.left = new Node(6); root.right.left.right = new Node(7); root.right.right.left = new Node(9); root.right.right.right = new Node(10); // Define the values of the nodes int[] node_values = { 2, 3, 4, 4, 7, 6, 2, 3, 9, 1 }; // Call the function to get the sum of nodes at // different levels getSum(node_values, root); }} |
Python3
# a binary tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = Nonedef newNode(data): return Node(data)def getSum(node_values, root): q = [] q.append(root) level = 0 while len(q) != 0: n = len(q) total = 0 for i in range(n): front_node = q.pop(0) total += node_values[front_node.data - 1] if front_node.left: q.append(front_node.left) if front_node.right: q.append(front_node.right) print(f"Sum of level {level} : {total}") level += 1# driver code to test above functionroot = newNode(1)root.left = newNode(2)root.right = newNode(3)root.left.left = newNode(4)root.right.left = newNode(5)root.right.right = newNode(8)root.right.left.left = newNode(6)root.right.left.right = newNode(7)root.right.right.left = newNode(9)root.right.right.right = newNode(10)node_values = [2, 3, 4, 4, 7, 6, 2, 3, 9, 1]# function call to get the sum# of nodes of different levelgetSum(node_values, root) |
Javascript
// a binary tree nodeclass Node { constructor(data) { this.data = data; this.left = null; this.right = null; }}function newNode(data) { return new Node(data);}function getSum(node_values, root) { let q = []; q.push(root); let level = 0; while(q.length !== 0){ let n = q.length; let sum = 0; for(let i = 0; i < n; i++){ let front_node = q.shift(); sum += node_values[front_node.data - 1]; if(front_node.left) q.push(front_node.left); if(front_node.right) q.push(front_node.right); } console.log(`Sum of level ${level} : ${sum}`); level++; }}// driver code to test above functionlet root = newNode(1);root.left = newNode(2);root.right = newNode(3);root.left.left = newNode(4);root.right.left = newNode(5);root.right.right = newNode(8);root.right.left.left = newNode(6);root.right.left.right = newNode(7);root.right.right.left = newNode(9);root.right.right.right = newNode(10);let node_values = [2, 3, 4, 4, 7, 6, 2, 3, 9, 1];// function call to get the sum// of nodes of different levelgetSum(node_values, root); |
C#
using System;using System.Collections.Generic;public class Node{ public int data; public Node left, right; public Node(int data){ this.data = data; this.left = this.right = null; }};public class Gfg{ public static Node newNode(int data){ return new Node(data); } public static void getSum(int[] node_values, Node root){ Queue<Node> q = new Queue<Node>(); q.Enqueue(root); int level = 0; while(q.Count != 0){ int n = q.Count; int sum = 0; for(int i = 0; i<n; i++){ Node front_node = q.Peek(); q.Dequeue(); sum += node_values[front_node.data - 1]; if(front_node.left != null) q.Enqueue(front_node.left); if(front_node.right != null) q.Enqueue(front_node.right); } Console.WriteLine("Sum of level "+level+" : "+sum); level++; } } public static void Main(){ Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.right.left = newNode(5); root.right.right = newNode(8); root.right.left.left = newNode(6); root.right.left.right = newNode(7); root.right.right.left = newNode(9); root.right.right.right = newNode(10); int[] node_values = new int[]{2,3,4,4,7,6,2,3,9,1}; // function call to get the sum // of nodes of different level getSum(node_values, root); }} |
Output
Sum of level 0 : 2 Sum of level 1 : 7 Sum of level 2 : 14 Sum of level 3 : 18
Time Complexity: O(N) where N is the number of nodes in given Binary Tree.
Auxiliary Space: O(N) due to queue data structure.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
