Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Solution Approach
2.1.
Algorithm 
2.2.
C++ code
2.3.
Algorithm Complexity
3.
Frequently Asked Questions
3.1.
What is the level order traversal of a tree?
3.2.
Why do we use a queue in a level order traversal of a tree?
4.
Conclusion
Last Updated: Mar 27, 2024

Maximum Level Sum in N-ary Tree

Author Riya
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Trees are popular Data Structures having a Wide Range of Applications. These are also among the popular topics that are asked about in interviews with top technology companies. There are numerous problems that involve the usage of Tree Data Structure and the operations that can be performed on trees.

This blog will discuss the "Maximum Level Sum in N-ary Tree" problem. In this problem, we will have an N-ary tree with 'N' vertices numbered from 0 to N, each vertex will have a value associated with it, and we have to find the maximum level order sum for this given tree. The level order sum refers to the sum of the values associated with all the vertices in that level of the tree.


Let's take an example to understand the problem:

Assume we have been given a tree with eight vertices numbered from 0 to 7 and an array 'val[8]', which denotes that vertex 'i' has a value 'val[i]' associated with it.

Here val[8] = {1, 8, 9, 7, 2, 3, 4, 6}

The tree is shown below:
 

N-Ary Tree

 

In this tree:

Sum for level 0 = val[0] = 1

Sum for level 1 = val[1] + val[2] + val[3] = 8 + 9 + 7 = 24

Sum for level 2 = val[4] + val[5] + val[6] + val[7] = 2 + 3 + 4 + 6 = 15

So, the maximum level order sum will be 24, which is the level order sum for level 1.

 

Now that we understand the problem of finding the maximum level order sum in N-ary tree let's discuss the approach.

 

Solution Approach

The approach to find the maximum level order traversal in N-ary tree is based on the level order traversal of a tree. We will do the level order traversal of the given N-ary tree,  calculate the level sum for each level and keep track of the maximum level sum. And, finally, after traversing all the levels, we will return the maximum level sum.

                     

Algorithm 

Step 1. Create a function "maximumLevelSum()' to find the maximum level sum in N-ary tree, which takes the following three inputs:

  1. N - Total number of nodes
  2. tree - A 2-D array representing the edges of the tree
  3. Val - A vector containing the values associated with each node in the tree

Step 2. Create the adjacency list representation of the tree using the array 'tree', which has stored all the edges of the tree

Step 3.  Initialize a variable "maxLevelSum" with the level sum of level 0. Now create a queue to store nodes while traversing the tree in level order.

Step 4. Perform level order traversal of the tree, store the sum for each level, and keep updating the variable "maxLevelSum" after traversing each level.

Step 5. Finally, after traversing the complete tree, return "maxLevelSum".

 

C++ code

// C++ program to find maximum level sum in N-ary tree
#include <bits/stdc++.h>
using namespace std;


// Function to find the maximum level sum in N-ary tree
int maximumLevelSum(int N, int tree[][2], vector<int> val)
{


// Creating the adjacency list representation for the tree
	vector<int> adj[N];
	for (int i = 0; i < (N - 1); i++)
	{
		adj[tree[i][0]].push_back(tree[i][1]);
	}


// Initialize the maximum level sum as the val[0] which is the level sum for level 0
	int maxLevelSum = val[0];


// Creating a queue to store the nodes of each level for performing the level order traversal
	queue<int> q;


// Inserting the root node into the queue
	q.push(0);


// level order traversal
	while (!q.empty())
	{


// Variable to store the number of nodes in the current level
		int curr_count = q.size();


		            // Variable to store the sum of current level
		int curr_sum = 0;


// Traverse the current level
		while (curr_count--)
		{


// Get the current node from the queue
			int curr_node = q.front();
			q.pop();


// Update sum of current level
			curr_sum = curr_sum + val[curr_node];


// Inserting the children of current node into the queue
			for (int i = 0; i < adj[curr_node].size(); i++)
			{
				q.push(adj[curr_node][i]);
			}
		}


// Update maximum level sum
		maxLevelSum = max(maxLevelSum, curr_sum);
	}


// Return the maximum level order sum
	return maxLevelSum;
}


// Driver Code
int main()
{
// Variable to store the number of nodes in the given tree
	int N = 8;


// 2-D array to store the edges of the N-ary tree
	int tree[][2] = { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 1, 4 }, { 1, 5 }, { 3, 6 }, { 6, 7 }, { 6, 8 }, { 6, 9 } };

// Vector to store the values associated with each of the vertices
	vector<int> val = {1, 8, 9, 7, 2, 3, 4, 6};


// Call the function to find the maximum level sum in N-ary tree
	cout << "The maximum level sum in N-ary tree given here is: " << maximumLevelSum(N, tree, val);


	return 0;
}

 

Output:
The maximum level sum in N-ary tree given here is: 24

Algorithm Complexity

Time Complexity: O(N)

In the function "maximumLevelSum()' to find the maximum level sum in the N-ary tree, we have traversed each node of the tree. So, the time complexity is O(N), where 'N' is the number of nodes in the tree.


Space Complexity: O(1) 

In the function "maximumLevelSum()' to find the maximum level sum in the N-ary tree, we have created a queue to store the tree's nodes. So the space complexity is O(N), where 'N' is the number of nodes in the tree.

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 level order traversal of a tree?

Level OrderTraversal is a breadth-first traversal of a tree in which we traverse the tree level-wise. In this, we first cover all the nodes of a present level and then move to the next level of the tree.

Why do we use a queue in a level order traversal of a tree?

In level order traversal, we need to traverse the nodes in the order in which they are stored, i.e., while traversing the current level of the tree, we store the children of these nodes, and we need to process those children nodes in an order in which they are stored. That's why we use a 'queue' data structure as it is a "First In First Out" type of data structure.

 

Conclusion

In this article, we discussed the problem "Maximum Level Sum in N-ary Tree", the solution approach, its C++ implementation, and its time and space complexity. If you want to solve tree data structure problems for practice, you can visit Coding Ninjas Studio.

Recommended Reading:

Recommended Problems:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Check if a binary tree contains node values are in strictly increasing and decreasing order at even and odd levels
Next article
Number of siblings of a given Node in n-ary Tree
Live masterclass