Introduction
Trees are one of the critical data structures. This article will discuss finding the maximum level sum in binary tree. Problems on trees are common in coding contests and asked in various technical interviews. Before moving on to the problem, it is essential to understand Trees and Queues well.
Problem Statement
We have a binary tree containing both positive and negative nodes. Given the root to a Binary tree, our goal is to find the maximum level sum in binary tree.
Sample Example
Input:
Root to the binary containing the value 1.
Output:
8
Explanation:
The maximum sum is 8 as the sum at level 1 is 1, at level 2 it’s 2+4 = 6, and at level 3 it’s 3 + 5 = 8, and the maximum of these is 8. Hence the answer is 8. Approach
Whenever we think of traversing the levels in a tree or a binary tree, the first thought that comes to mind is using the BFS traversal which traverses the tree level wise. At each level we can find the sum of nodes at that level and maximise the answer. This approach will lead us to our answer as our goal is to find the maximum level sum in Binary Tree.
PseudoCode
Algorithm
___________________________________________________________________
procedure MaxLevelSumInBinaryTree(rootNode):
___________________________________________________________________
1. Queue q ← an empty queue # to find the given node.
2. maxLevelSum ← -∞
3. q.push(rootNode)
4. while q is not empty do
5. curLevelSize ← q.size(), curLevelSum ←0
6. for all node at currentLevel in q till curLevelSize:
7. if node.children exist do
8. q.push(node.children)
9. curLevelSum ← curLevelSum + node.val
9. end if
10. end for
11. maxLevelSum ←max(maxLevelSum, curLevelSum)
12. end while
13. return maxLevelSum
14. end procedure
___________________________________________________________________
Implementation in C++
// program to find the maximum level sum in binary tree
#include <bits/stdc++.h>
#define Node struct BinaryTreeNode
using namespace std;
// creating a binary tree node struct
struct BinaryTreeNode{
int val; // value of the node
Node* left; // left child
Node* right; // right child
BinaryTreeNode(int v){
this->val = v;
}
};
// function to find the maximum Level Sum In Binary Tree
int maximumLevelSumInBinaryTree(Node* root){
// check if the root is nullptr
if(root==nullptr) return 0;
// initialise the maxLevelSum to -infinity
int maxLevelSum = INT_MIN;
// queue to store nodes at a level and perform a BFS
queue<Node*> q;
// push the root Node
q.push(root);
// run until nodes at all levels are traversed
while(!q.empty()){
// current Size of queue
int curLevelSize = q.size();
// sum at current Level
int curLevelSum = 0;
// loop over all nodes in the curren level
while(curLevelSize--){
Node* top = q.front(); q.pop();
// add it to the curLevelSum
curLevelSum += top->val;
// add its children meanwhile for the next Level sum computation
if(top->left)
q.push(top->left);
if(top->right)
q.push(top->right);
}
// maximise the maxLevelSum
maxLevelSum = max(maxLevelSum, curLevelSum);
}
// return the sum
return maxLevelSum;
}
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(4);
root->left->left = new Node(3);
root->left->right = new Node(5);
cout<<"The maximum Level Sum In Binary Tree: "<<maximumLevelSumInBinaryTree(root);
return 0;
}
Output:
8
Complexity Analysis
Time complexity- the time complexity will be O(n) as we are traversing all the nodes of the binary tree once.
Space Complexity: the space complexity is O(n) as we are using a queue which can store O(n) nodes at max.
Check out this problem - Diameter Of Binary Tree
84+ registered