Given a Binary Tree, the task is to find the sum of leaf nodes at every level of the given tree.
Examples:
Input:
Output:
0
0
6
30
12
Explanation:
Level 1: No leaf node, so sum = 0
Level 2: No leaf node, so sum = 0
Level 3: One leaf node: 6, so sum = 6
Level 4: Three leaf nodes: 9, 10, 11, so sum = 30
Level 5: One leaf node: 12, so sum = 12Input:
Output:
0
0
6
28
Approach: The given problem can be solved by using the Level Order Traversal. Follow the steps below to solve the given problem:
- Create a queue qu, to store the node alongside its level. Also, create a map to store the sum of each level.
- Perform the level order traversal from the root node and store each node with its level in the queue, and also check the current node for the leaf node. If it’s a leaf node then add its value in the map corresponding to its level.
- After completing the above steps, print the values in the map as the sum of each level of the given tree.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Tree node structureclass Node {public: int data; Node *left, *right; Node(int data) { this->data = data; left = right = NULL; }};// Function to print the sum of leaf nodes// at each horizontal levelvoid printLevelSum(Node* root){ if (root == NULL) { cout << "No nodes present\n"; return; } // Map to hold sum at each level map<int, int> mp; // Queue to hold tree node with level queue<pair<Node*, int> > q; // Root node is at level 1 q.push({ root, 1 }); pair<Node*, int> p; // Level Order Traversal of tree while (!q.empty()) { p = q.front(); q.pop(); // Create a key for each level // in the map if (mp.find(p.second) == mp.end()) { mp[p.second] = 0; } // If current node is a leaf node if (p.first->left == NULL && p.first->right == NULL) { // Adding value in the map // corresponding to its level mp[p.second] += p.first->data; } if (p.first->left) q.push({ p.first->left, p.second + 1 }); if (p.first->right) q.push({ p.first->right, p.second + 1 }); } // Print the sum at each level for (auto i : mp) { cout << i.second << endl; }}// Driver Codeint main(){ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->right = new Node(8); root->left->right->right = new Node(9); root->right->right->left = new Node(10); root->right->right->right = new Node(11); root->left->left->right->right = new Node(12); printLevelSum(root); return 0;} |
Java
// Java program for the above approachimport java.util.LinkedList;import java.util.Map;import java.util.Queue;import java.util.HashMap;public class Print_Level_Sum_Btree { /* A tree node structure */ static class Node { int data; Node left; Node right; Node(int data){ this.data = data; left = null; right = null; } } // User defined class Pair to hold // the node and its level static class Pair{ Node n; int i; Pair(Node n, int i){ this.n = n; this.i = i; } } // Function to print the sum of leaf nodes // at each horizontal level static void printLevelSum(Node root) { if (root == null) { System.out.println("No nodes present"); return; } // hashmap to hold sum at each level HashMap<Integer, Integer> map = new HashMap<>(); // queue to hold tree node with level Queue<Pair> q = new LinkedList<Pair>(); // Root node is at level 1 q.add(new Pair(root, 1)); Pair p; // Level Order Traversal of tree while (!q.isEmpty()) { p = q.peek(); q.remove(); // Create a key for each level // in the map if (!map.containsKey(p.i)) map.put(p.i, 0); // If current node is a leaf node if (p.n.left == null && p.n.right == null) { // Adding value in the map // corresponding to its level map.put(p.i, map.get(p.i) + p.n.data); } if (p.n.left != null) q.add(new Pair(p.n.left, p.i + 1)); if (p.n.right != null) q.add(new Pair(p.n.right, p.i + 1)); } // Print the sum at each level for (Map.Entry mapElement : map.entrySet()) { int value = ((int)mapElement.getValue()); System.out.println(value); } } // Driver Code public static void main(String args[]) { Node root = null; root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.right = new Node(8); root.left.right.right = new Node(9); root.right.right.left = new Node(10); root.right.right.right = new Node(11); root.left.left.right.right = new Node(12); printLevelSum(root); }}// This code is contributed by vineetsharma36. |
Python3
# Python3 program for the above approachclass newNode: # Construct to create a new node def __init__(self, key): self.data = key self.left = None self.right = None# Function to print the sum of leaf nodes# at each horizontal leveldef printLevelSum(root): if (not root): print("No nodes present") return # Dictionary to hold sum at each level dict = {} # queue to hold tree node with level q = [] # Root node is at level 1 q.append([root, 1]) p = [] # Level order Traversal of Tree while (len(q)): p=q[0] q.pop(0) # Create a key for each level # in the dictionary if (p[1] not in dict.keys()): dict[p[1]] = 0 # If current node is a leaf node if (not p[0].left and not p[0].right): # Adding value in the dictionary # corresponding to its level dict[p[1]] = p[0].data + dict.get(p[1]) if (p[0].left): q.append([p[0].left, p[1] + 1]) if (p[0].right): q.append([p[0].right, p[1] + 1]) # Print the sum at each level for sum in dict.values(): print(sum)# Driver Codeif __name__ == '__main__': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) root.right.left = newNode(6) root.right.right = newNode(7) root.left.left.right = newNode(8) root.left.right.right = newNode(9) root.right.right.left = newNode(10) root.right.right.right = newNode(11) root.left.left.right.right = newNode(12) printLevelSum(root) # This code is contributed by vineetsharma36. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class Print_Level_Sum_Btree { /* A tree node structure */ public class Node { public int data; public Node left; public Node right; public Node(int data){ this.data = data; left = null; right = null; } } // User defined class Pair to hold // the node and its level public class Pair{ public Node n; public int i; public Pair(Node n, int i){ this.n = n; this.i = i; } } // Function to print the sum of leaf nodes // at each horizontal level static void printLevelSum(Node root) { if (root == null) { Console.WriteLine("No nodes present"); return; } // hashmap to hold sum at each level Dictionary<int, int> map = new Dictionary<int,int>(); // queue to hold tree node with level Queue<Pair> q = new Queue<Pair>(); // Root node is at level 1 q.Enqueue(new Pair(root, 1)); Pair p; // Level Order Traversal of tree while (q.Count!=0) { p = q.Peek(); q.Dequeue(); // Create a key for each level // in the map if (!map.ContainsKey(p.i)) map.Add(p.i, 0); // If current node is a leaf node if (p.n.left == null && p.n.right == null) { // Adding value in the map // corresponding to its level map[p.i]= map[p.i] + p.n.data; } if (p.n.left != null) q.Enqueue(new Pair(p.n.left, p.i + 1)); if (p.n.right != null) q.Enqueue(new Pair(p.n.right, p.i + 1)); } // Print the sum at each level foreach(KeyValuePair<int, int> entry in map){ int value = (entry.Value); Console.WriteLine(value); } } // Driver Code public static void Main(String []args) { Node root = null; root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.right = new Node(8); root.left.right.right = new Node(9); root.right.right.left = new Node(10); root.right.right.right = new Node(11); root.left.left.right.right = new Node(12); printLevelSum(root); }}// This code is contributed by umadevi9616 |
Javascript
<script>// Javascript program for the above approach// Tree node structureclass Node { constructor(data) { this.data = data; this.left = this.right = null; }}// Function to print the sum of leaf nodes// at each horizontal levelfunction printLevelSum(root) { if (root == null) { document.write("No nodes present\n"); return; } // Map to hold sum at each level let mp = new Map(); // Queue to hold tree node with level let q = []; // Root node is at level 1 q.push([root, 1]); let p = []; // Level Order Traversal of tree while (q.length) { p = q[q.length - 1]; q.pop(); // Create a key for each level // in the map if (!mp.has(p[1])) { mp.set(p[1], 0); } // If current node is a leaf node if (p[0].left == null && p[0].right == null) { // Adding value in the map // corresponding to its level mp.set(p[1], mp.get(p[1]) + p[0].data); } if (p[0].left) q.push([p[0].left, p[1] + 1]); if (p[0].right) q.push([p[0].right, p[1] + 1]); } // Print the sum at each level for (let i of mp) { document.write(i[1] + "<bR>"); }}// Driver Codelet root = new Node(1);root.left = new Node(2);root.right = new Node(3);root.left.left = new Node(4);root.left.right = new Node(5);root.right.left = new Node(6);root.right.right = new Node(7);root.left.left.right = new Node(8);root.left.right.right = new Node(9);root.right.right.left = new Node(10);root.right.right.right = new Node(11);root.left.left.right.right = new Node(12);printLevelSum(root);</script> |
Output
0 0 6 30 12
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Approach(Recursive):
Follow the below steps to solve the problem:
1). In this method we will traverse the each node of binary tree recursively and keep track of level with each node.
2). If the current node is leaf node then we will store the node value in vector otherwise if the node is not leaf node then we will add the sum in 0 so it will not effects out answer.
3). Finally print the array of answers.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// struct of binary tree nodestruct Node{ int data; Node* left; Node* right; Node(int data){ this->data = data; this->left = NULL; this->right = NULL; }};// function to find the height of binary treeint height(Node* root){ if(root == NULL) return 0; int l = height(root->left); int r = height(root->right); return max(l,r)+1;}// Function to print the sum of leaf nodes// at each horizontal levelvoid printLevelSum(Node* root, vector<int> &ans, int level){ if(root == NULL) return; if(root->left == NULL && root->right == NULL){ ans[level] += root->data; }else{ ans[level] += 0; } printLevelSum(root->left, ans, level+1); printLevelSum(root->right, ans, level+1);}//driver codeint main(){ Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->right = new Node(8); root->left->right->right = new Node(9); root->right->right->left = new Node(10); root->right->right->right = new Node(11); root->left->left->right->right = new Node(12); vector<int> ans(height(root), 0); printLevelSum(root, ans, 0); for(int i : ans) cout<<i<<endl; return 0;}// This code is contributed by Yash Agarwal(yashagarwal2852002) |
Java
import java.util.*;// Node class for binary treeclass Node { int data; Node left, right; public Node(int data) { this.data = data; left = right = null; }} // Class for the binary treeclass BinaryTree { Node root; // Function to find the height of binary tree int height(Node node) { if (node == null) return 0; int lheight = height(node.left); int rheight = height(node.right); return Math.max(lheight, rheight) + 1; } // Function to print the sum of leaf nodes // at each horizontal level void printLevelSum(Node node, int[] ans, int level) { if (node == null) return; if (node.left == null && node.right == null) { ans[level] += node.data; } else { ans[level] += 0; } printLevelSum(node.left, ans, level + 1); printLevelSum(node.right, ans, level + 1); } // Driver code public static void main(String args[]) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.left.left.right = new Node(8); tree.root.left.right.right = new Node(9); tree.root.right.right.left = new Node(10); tree.root.right.right.right = new Node(11); tree.root.left.left.right.right = new Node(12); int[] ans = new int[tree.height(tree.root)]; tree.printLevelSum(tree.root, ans, 0); for (int i : ans) { System.out.println(i); } }} |
Python
# Python program for the above approach# class of binary tree nodeclass Node: def __init__(self, data): self.data = data self.left = None self.right = None# function to find the height of binary treedef height(root): if root is None: return 0 l = height(root.left) r = height(root.right) return max(l, r) + 1# function to print the sum of leaf nodes# at each horizontal leveldef printLevelSum(root, ans, level): if root is None: return if root.left is None and root.right is None: ans[level] += root.data else: ans[level] += 0 printLevelSum(root.left, ans, level+1) printLevelSum(root.right, ans, level+1)# driver codeif __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) root.left.left.right = Node(8) root.left.right.right = Node(9) root.right.right.left = Node(10) root.right.right.right = Node(11) root.left.left.right.right = Node(12) ans = [0] * height(root) printLevelSum(root, ans, 0) for i in ans: print(i) |
C#
// C# codeusing System;using System.Collections.Generic;public class Node{ public int data; public Node left, right; public Node(int data) { this.data = data; left = right = null; }}public class BinaryTree{ public Node root; // Function to find the height of binary tree public int height(Node node) { if (node == null) return 0; int lheight = height(node.left); int rheight = height(node.right); return Math.Max(lheight, rheight) + 1; } // Function to print the sum of leaf nodes // at each horizontal level public void printLevelSum(Node node, int[] ans, int level) { if (node == null) return; if (node.left == null && node.right == null) { ans[level] += node.data; } else { ans[level] += 0; } printLevelSum(node.left, ans, level + 1); printLevelSum(node.right, ans, level + 1); } // Driver code public static void Main(string[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.left.left.right = new Node(8); tree.root.left.right.right = new Node(9); tree.root.right.right.left = new Node(10); tree.root.right.right.right = new Node(11); tree.root.left.left.right.right = new Node(12); int[] ans = new int[tree.height(tree.root)]; tree.printLevelSum(tree.root, ans, 0); foreach (int i in ans) { Console.WriteLine(i); } }} |
Javascript
// JavaScript program for the above approach// structure of binary tree nodeclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}// function to find the height of binary treefunction height(root){ if(root == null) return 0; let l = height(root.left); let r = height(root.right); return Math.max(l,r)+1;}let ans;// Function to print the sum of leaf nodes// at each horizontal levelfunction printLevelSum(root, level){ if(root == null) return; if(root.left == null && root.right == null){ ans[level] += root.data; }else{ ans[level] += 0; } printLevelSum(root.left, level+1); printLevelSum(root.right, level+1);}// driver codelet root = new Node(1);root.left = new Node(2);root.right = new Node(3);root.left.left = new Node(4);root.left.right = new Node(5);root.right.left = new Node(6);root.right.right = new Node(7);root.left.left.right = new Node(8);root.left.right.right = new Node(9);root.right.right.left = new Node(10);root.right.right.right = new Node(11);root.left.left.right.right = new Node(12);ans = new Array(height(root)).fill(0);printLevelSum(root, 0);for(let i = 0; i<ans.length; i++){ console.log(ans[i]);}// THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999) |
Output
0 0 6 30 12
Time Complexity: O(N) where N is the number of nodes in given binary tree.
Auxiliary Space: O(h) where h is the height of binary tree due to recursion.
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!
