Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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.
Frequently Asked Questions
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

Author 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

Frequently Asked Questions

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!!