1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
PseudoCode
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
3.1.
What is the maximum number of nodes in a binary tree of depth k?
3.2.
Which are the different traversals of binary tree?
3.3.
What is the degree of a node in a tree?
4.
Conclusion
Last Updated: Mar 27, 2024

# Maximum Level Sum in Binary Tree

aniket verma
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## 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 is not empty do

5.      curLevelSize ← q.size(), curLevelSum ←0

6.          for all node at currentLevel intill 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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

### What is the maximum number of nodes in a binary tree of depth k?

The maximum number of nodes in a binary tree of depth k is 2k−1, k≥1.

### Which are the different traversals of binary tree?

There are four common traversals of a binary tree which are postOrder, preOrder, inOrder and levelOrder traversal.

### What is the degree of a node in a tree?

The degree of a node is the number of its children.

## Conclusion

This article taught us how to solve the problem of finding the maximum level sum in binary tree. We saw the implementation of the code in c++ using examples. We also analyzed the time and space complexity for the same.

Recommended problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!