Given a Binary Tree, return following value for it.
- For every level, compute sum of all leaves if there are leaves at this level. Otherwise ignore it.
- Return multiplication of all sums.
Examples:
Input: Root of below tree
2
/ \
7 5
\
9
Output: 63
First levels doesn't have leaves. Second level
has one leaf 7 and third level also has one
leaf 9. Therefore result is 7*9 = 63
Input: Root of below tree
2
/ \
7 5
/ \ \
8 6 9
/ \ / \
1 11 4 10
Output: 208
First two levels don't have leaves. Third
level has single leaf 8. Last level has four
leaves 1, 11, 4 and 10. Therefore result is
8 * (1 + 11 + 4 + 10)
In the previous article we have seen a Queue based solution using level order traversal.
Here, we are simply doing preorder traversal of the binary tree, and we have used unordered_map in C++ STL to store sum of leaf nodes at same level. Then in a single traversal of the map, we’ve calculated the final product of level sums.
Below is the implementation of above approach:
C++
// C++ program to find product of sums// of data of leaves at same levels// using map in STL#include <bits/stdc++.h>using namespace std;// Binary Tree Nodestruct Node { int data; Node* left; Node* right;};// Utility function to create// a new Tree nodeNode* newNode(int data){ Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp;}// Helper function to calculate sum of// leaf nodes at same level and store in// an unordered_mapvoid productOfLevelSumUtil(Node* root, unordered_map<int, int>& level_sum, int level){ if (!root) return; // Check if current node is a leaf node // If yes add it to sum of current level if (!root->left && !root->right) level_sum[level] += root->data; // Traverse left subtree productOfLevelSumUtil(root->left, level_sum, level + 1); // Traverse right subtree productOfLevelSumUtil(root->right, level_sum, level + 1);}// Function to calculate product of level sumsint productOfLevelSum(Node* root){ // Create a map to store sum of leaf // nodes at same levels. unordered_map<int, int> level_sum; // Call the helper function to // calculate level sums of leaf nodes productOfLevelSumUtil(root, level_sum, 0); // variable to store final product int prod = 1; // Traverse the map to calculate product // of level sums for (auto it = level_sum.begin(); it != level_sum.end(); it++) prod *= it->second; // Return the result return prod;}// Driver Codeint main(){ // Creating Binary Tree Node* root = newNode(2); root->left = newNode(7); root->right = newNode(5); root->left->right = newNode(6); root->left->left = newNode(8); root->left->right->left = newNode(1); root->left->right->right = newNode(11); root->right->right = newNode(9); root->right->right->left = newNode(4); root->right->right->right = newNode(10); cout << "Final product is = " << productOfLevelSum(root) << endl; return 0;} |
Java
// Java program to find product of sums// of data of leaves at same levels// using map in STLimport java.util.*;public class GFG{ // Binary Tree Node static class Node { int data; Node left, right; Node(int item) { data = item; left = right = null; } } // Root of the Binary Tree Node root; public GFG() { root = null; } // Utility function to create // a new Tree node static Node newNode(int data) { Node temp = new Node(data); return (temp); } // Create a map to store sum of leaf // nodes at same levels. static HashMap<Integer, Integer> level_sum = new HashMap<>(); // Helper function to calculate sum of // leaf nodes at same level and store in // an unordered_map static void productOfLevelSumUtil(Node root, int level) { if (root == null) return; // Check if current node is a leaf node // If yes add it to sum of current level if (root.left == null && root.right == null) { if(level_sum.containsKey(level)) { level_sum.put(level, level_sum.get(level) + root.data); } else{ level_sum.put(level, root.data); } } // Traverse left subtree productOfLevelSumUtil(root.left, level + 1); // Traverse right subtree productOfLevelSumUtil(root.right, level + 1); } // Function to calculate product of level sums static int productOfLevelSum(Node root) { // Call the helper function to // calculate level sums of leaf nodes productOfLevelSumUtil(root, 0); // variable to store final product int prod = 1; // Traverse the map to calculate product // of level sums for (Map.Entry<Integer, Integer> it : level_sum.entrySet()) { prod *= it.getValue(); } // Return the result return prod; } public static void main(String[] args) { // Creating Binary Tree GFG tree = new GFG(); tree.root = newNode(2); tree.root.left = newNode(7); tree.root.right = newNode(5); tree.root.left.right = newNode(6); tree.root.left.left = newNode(8); tree.root.left.right.left = newNode(1); tree.root.left.right.right = newNode(11); tree.root.right.right = newNode(9); tree.root.right.right.left = newNode(4); tree.root.right.right.right = newNode(10); System.out.print("Final product is = " + productOfLevelSum(tree.root)); }}// This code is contributed by divyeshrabadiya07. |
Python3
# Python program to find product of sums# of data of leaves at same levels# using map# Binary Tree Node class Node: def __init__(self, data): self.left = None self.right = None self.data = data# Utility function to create# a new Tree nodedef newNode(data): temp = Node(data) return temp# Create a map to store sum of leaf# nodes at same levels.level_sum = {}# Helper function to calculate sum of# leaf nodes at same level and store in# a dictionarydef productOfLevelSumUtil(root, level): if root is None: return # Check if current node is a leaf node # If yes add it to sum of current level if root.left is None and root.right is None: if level in level_sum: level_sum[level] += root.data else: level_sum[level] = root.data # Traverse left subtree productOfLevelSumUtil(root.left, level + 1) # Traverse right subtree productOfLevelSumUtil(root.right, level + 1)# Function to calculate product of level sumsdef productOfLevelSum(root): # Call the helper function to # calculate level sums of leaf nodes productOfLevelSumUtil(root, 0) # variable to store final product prod = 1 # Traverse the dictionary to calculate product # of level sums for key in level_sum: prod *= level_sum[key] # Return the result return prod# Creating Binary Treeroot = newNode(2)root.left = newNode(7)root.right = newNode(5)root.left.right = newNode(6)root.left.left = newNode(8)root.left.right.left = newNode(1);root.left.right.right = newNode(11);root.right.right = newNode(9);root.right.right.left = newNode(4);root.right.right.right = newNode(10);print("Final product is = " + str(productOfLevelSum(root)));#This code is contributed by Potta Lokesh |
C#
// C# program to find product of sums// of data of leaves at same levels// using map in STLusing System;using System.Collections;using System.Collections.Generic;// Binary Tree Nodeclass Node { public int data; public Node left, right; public Node(int item) { data = item; left = right = null; }} public class GFG { // Root of the Binary Tree Node root; public GFG() { root = null; } // Utility function to create // a new Tree node static Node newNode(int data) { Node temp = new Node(data); return (temp); } // Create a map to store sum of leaf // nodes at same levels. static Dictionary<int, int> level_sum = new Dictionary<int, int>(); // Helper function to calculate sum of // leaf nodes at same level and store in // an unordered_map static void productOfLevelSumUtil(Node root, int level) { if (root == null) return; // Check if current node is a leaf node // If yes add it to sum of current level if (root.left == null && root.right == null) { if(level_sum.ContainsKey(level)) { level_sum[level] += root.data; } else{ level_sum[level] = root.data; } } // Traverse left subtree productOfLevelSumUtil(root.left, level + 1); // Traverse right subtree productOfLevelSumUtil(root.right, level + 1); } // Function to calculate product of level sums static int productOfLevelSum(Node root) { // Call the helper function to // calculate level sums of leaf nodes productOfLevelSumUtil(root, 0); // variable to store final product int prod = 1; // Traverse the map to calculate product // of level sums foreach(KeyValuePair<int, int> it in level_sum) { prod *= it.Value; } // Return the result return prod; } static void Main() { // Creating Binary Tree GFG tree = new GFG(); tree.root = newNode(2); tree.root.left = newNode(7); tree.root.right = newNode(5); tree.root.left.right = newNode(6); tree.root.left.left = newNode(8); tree.root.left.right.left = newNode(1); tree.root.left.right.right = newNode(11); tree.root.right.right = newNode(9); tree.root.right.right.left = newNode(4); tree.root.right.right.right = newNode(10); Console.Write("Final product is = " + productOfLevelSum(tree.root)); }}// This code is contributed by decode2207. |
Javascript
<script> // JavaScript program to find product of sums // of data of leaves at same levels // using map in STL // Binary Tree Node class Node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Utility function to create // a new Tree node function newNode(data) { let temp = new Node(data); return temp; } // Create a map to store sum of leaf // nodes at same levels. let level_sum = new Map(); // Helper function to calculate sum of // leaf nodes at same level and store in // an unordered_map function productOfLevelSumUtil(root, level) { if (root == null) return; // Check if current node is a leaf node // If yes add it to sum of current level if (root.left == null && root.right == null) { if(level_sum.has(level)) { level_sum.set(level, level_sum.get(level) + root.data); } else{ level_sum.set(level, root.data); } } // Traverse left subtree productOfLevelSumUtil(root.left, level + 1); // Traverse right subtree productOfLevelSumUtil(root.right, level + 1); } // Function to calculate product of level sums function productOfLevelSum(root) { // Call the helper function to // calculate level sums of leaf nodes productOfLevelSumUtil(root, 0); // variable to store final product let prod = 1; // Traverse the map to calculate product // of level sums level_sum.forEach((value,it)=>{ prod *= value; }) // Return the result return prod; } // Creating Binary Tree let root = newNode(2); root.left = newNode(7); root.right = newNode(5); root.left.right = newNode(6); root.left.left = newNode(8); root.left.right.left = newNode(1); root.left.right.right = newNode(11); root.right.right = newNode(9); root.right.right.left = newNode(4); root.right.right.right = newNode(10); document.write("Final product is = " + productOfLevelSum(root));</script> |
Output
Final product is = 208
Complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(N)
Where N is the number of nodes in the Binary Tree
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!
