## 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__