Find multiplication of sums of data of leaves at sane levels - GeeksforGeeks
Given a Binary Tree, return following value for it.
1) For every level, compute sum of all leaves if there are leaves at this level. Otherwise ignore it.
2) Return multiplication of all sums.
Read full article from Find multiplication of sums of data of leaves at sane levels - GeeksforGeeks
Given a Binary Tree, return following value for it.
1) For every level, compute sum of all leaves if there are leaves at this level. Otherwise ignore it.
2) Return multiplication of all sums.
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)
One Simple Solution is to recursively compute leaf sum for all level starting from top to bottom. Then multiply sums of levels which have leaves. Time complexity of this solution would be O(n2).
An Efficient Solution is to use Queue based level order traversal. While doing the traversal, process all different levels separately. For every processed level, check if it has a leaves. If it has then compute sum of leaf nodes. Finally return product of all sums.
/* Calculate sum of all leaf Nodes at each level and returns multiplication of sums */int sumAndMultiplyLevelData(Node *root){ // Tree is empty if (!root) return 0; int mul = 1; /* To store result */ // Create an empty queue for level order tarversal queue<Node *> q; // Enqueue Root and initialize height q.push(root); // Do level order traversal of tree while (1) { // NodeCount (queue size) indicates number of Nodes // at current lelvel. int NodeCount = q.size(); // If there are no Nodes at current level, we are done if (NodeCount == 0) break; // Initialize leaf sum for current level int levelSum = 0; // A boolean variable to indicate if found a leaf // Node at current level or not bool leafFound = false; // Dequeue all Nodes of current level and Enqueue all // Nodes of next level while (NodeCount > 0) { // Process next Node of current level Node *Node = q.front(); /* if Node is a leaf, update sum at the level */ if (isLeaf(Node)) { leafFound = true; levelSum += Node->data; } q.pop(); // Add children of Node if (Node->left != NULL) q.push(Node->left); if (Node->right != NULL) q.push(Node->right); NodeCount--; } // If we found at least one leaf, we multiply // result with level sum. if (leafFound) mul *= levelSum; } return mul; // Return result}