1161. Maximum Level Sum of a Binary Tree

MediumTreeDepth-First SearchBreadth-First SearchBinary Tree
Leetcode Link

Problem Description

The problem provides us with the root of a binary tree and asks us to find the level with the maximum sum of node values. In a binary tree, each node has at most two children. The root of the tree is at level 1, its children are at level 2, and this pattern continues for subsequent levels. We need to determine the smallest level number x, which has the maximum sum compared to sums of nodes at other levels.

Intuition

To solve this problem, we can use breadth-first search (BFS), which is an algorithm that starts at the tree root and explores all nodes at the present depth level before moving on to nodes at the next depth level. This approach is suitable because it naturally processes nodes level by level. Here's how we can use BFS to solve the problem:

  • Initialize a queue that will hold the nodes to be processed, and start with the root node.
  • Initialize variables to keep track of the maximum sum (mx), the current level (i), and the level with the maximum sum (ans).
  • For each level, we process all nodes on that level to calculate the sum of values at the current level (s).
  • After processing all nodes at the current level, we compare the sum with mx. If the sum of the current level exceeds mx, we update mx to this sum and record the current level number as ans since it's the smallest level with this new maximum sum so far.
  • Continue the process for all levels until all nodes have been processed.
  • Return the level number ans, which corresponds to the smallest level with the maximal sum.

The provided solution implements this BFS approach efficiently.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

How many times is a tree node visited in a depth first search?

Solution Approach

The Reference Solution Approach applies the breadth-first search (BFS) pattern using a queue to traverse the binary tree level by level. Here is the walk-through of the implementation steps:

  1. Start by initializing a queue q with the root node of the tree. This queue will store the nodes to be processed for each level.

  2. We track the maximum sum encountered so far with mx, set initially to negative infinity (-inf), since we want to be able to compare it with sums that can be potentially zero or positive.

  3. The current level i is set to 0 at the beginning. It will be incremented as we start processing each level to keep track of the level number.

  4. We enter a while loop that continues as long as there are nodes left in the queue q.

    • Increment the level i by one as we are beginning to process a new level.

    • Initialize a sum s for the current level which will be used to add up all node values at this level.

    • Use a for loop to process each node at the current level. The range is determined by the number of elements in the queue at the start of the level (len(q)).

      • Dequeue the front node of the queue and add its value to s.

      • If the current node has a left child, enqueue the left child.

      • Similarly, if the current node has a right child, enqueue the right child.

  5. After the for loop ends, all nodes at the current level have been processed. We now compare the sum s of the current level to the max sum mx.

    • If s is greater than mx, we update mx to s and record the current level as ans because it's currently the level with the highest sum.

  6. Once the queue is empty, meaning all levels have been processed, we exit the while loop.

  7. Finally, return the variable ans, which holds the smallest level number with the greatest sum.

By using a queue alongside the BFS pattern, the solution ensures that the tree is traversed level by level, summing node values effectively and keeping track of the level with the greatest sum.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Example Walkthrough

Let's consider a small binary tree as an example to illustrate the solution approach:

1        3
2       / \
3      9  20
4        /  \
5       15   7

In this tree, the root node has a value of 3, the root's left child has a value of 9, and the root's right child has a value of 20 which further has two children with values 15 and 7.

Here is how the BFS algorithm would process this tree to find the level with the maximum sum:

  1. We start by initializing the queue q with the root node (value 3).

  2. The maximum sum mx is initialized to negative infinity, and the current level i is set to 0.

  3. Enter the while loop to begin processing since the queue is not empty.

  4. Increment i to 1 since we are now on level 1, and initialize the sum s to 0.

  5. Process all nodes at level 1:

    • There is only one node, which is the root node with value 3.
    • Add this value to s, so now s = 3.
    • Enqueue its children (nodes with values 9 and 20) to the queue.

  6. Now, s is compared to mx. Since s (3) is greater than mx (-โˆž), update mx to 3 and mark the current level ans as 1.

  7. Move to the next level (level 2):

    • Increment i to 2.
    • The sum s is reset to 0.
    • There are two nodes at this level, with values 9 and 20. Process each by dequeuing and adding their values to s.
    • s is now 9 + 20 = 29.
    • Enqueue the children of these nodes (values 15 and 7) to the queue.

  8. Now, s (29) is compared to mx (3). s is larger so we update mx to 29 and ans to 2 because this level has the new maximum sum.

  9. Move to the next level (level 3):

    • Increment i to 3.
    • The sum s is reset to 0.
    • There are two nodes at this level, with values 15 and 7. Process each by dequeuing and adding their values to s.
    • s is now 15 + 7 = 22.

  10. Now, s (22) is compared to mx (29). Since s is less than mx, we do not update mx or ans.

  11. Since the queue is now empty, we have processed all levels.

  12. Return ans, which is 2, as level 2 has the maximum sum of 29.

Using the BFS approach outlined above, we traversed the given binary tree level by level, efficiently calculating the sum of node values at each level and identifying the level with the maximum sum.

Solution Implementation

1from collections import deque
2from math import inf
3
4# Definition for a binary tree node.
5class TreeNode:
6    def __init__(self, val=0, left=None, right=None):
7        self.val = val
8        self.left = left
9        self.right = right
10
11class Solution:
12    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
13        # Initialize the queue with the root node
14        queue = deque([root])
15        # Initialize max_sum to negative infinity to ensure any level's sum will be larger
16        max_sum = -inf
17        # Initialize level counter to 0
18        level = 0
19        # Initialize answer to store the level with the maximum sum
20        answer = 0
21      
22        # Traverse the tree level by level using breadth-first search
23        while queue:
24            level += 1
25            current_sum = 0
26            # Process all the nodes at the current level
27            for _ in range(len(queue)):
28                # Pop the leftmost node from the queue
29                node = queue.popleft()
30                # Add the node's value to the current level's sum
31                current_sum += node.val
32                # If the node has a left child, add it to the queue
33                if node.left:
34                    queue.append(node.left)
35                # If the node has a right child, add it to the queue
36                if node.right:
37                    queue.append(node.right)
38            # Update max_sum and answer if the current level's sum is greater than max_sum
39            if max_sum < current_sum:
40                max_sum = current_sum
41                answer = level
42      
43        # Return the level that had the maximum sum
44        return answer
45
1class Solution {
2    // Function to find the level of the binary tree with the maximum sum
3    public int maxLevelSum(TreeNode root) {
4        // Queue to store nodes of tree level-wise
5        Deque<TreeNode> queue = new ArrayDeque<>();
6        // Adding the root to the queue as the starting point
7        queue.offer(root);
8      
9        // Variables to keep track of the maximum level sum and corresponding level
10        int maxSum = Integer.MIN_VALUE; // Initialized to minimum value
11        int level = 0;                  // Level counter
12        int maxLevel = 0;               // Level with max sum
13      
14        // Loop through each level of the tree
15        while (!queue.isEmpty()) {
16            level++; // Increment the level counter
17            int levelSum = 0; // Reset the level sum for the current level
18          
19            // Calculate the sum of all nodes at the current level
20            for (int count = queue.size(); count > 0; count--) {
21                TreeNode node = queue.pollFirst(); // Get the next node from the queue
22                levelSum += node.val;              // Add the node's value to the level sum
23              
24                // Add child nodes to the queue for the next level
25                if (node.left != null) {
26                    queue.offer(node.left);
27                }
28                if (node.right != null) {
29                    queue.offer(node.right);
30                }
31            }
32          
33            // Update max sum and corresponding level if the current level has a greater sum
34            if (maxSum < levelSum) {
35                maxSum = levelSum;
36                maxLevel = level;
37            }
38        }
39      
40        // Return the level with the maximum sum
41        return maxLevel;
42    }
43}
44
45// Definition for a binary tree node.
46class TreeNode {
47    int val;         // Node's value
48    TreeNode left;   // Reference to the left child node
49    TreeNode right;  // Reference to the right child node
50
51    // Constructors for TreeNode
52    TreeNode() {}
53    TreeNode(int val) { this.val = val; }
54    TreeNode(int val, TreeNode left, TreeNode right) {
55        this.val = val;
56        this.left = left;
57        this.right = right;
58    }
59}
60
1#include <queue>
2#include <climits>  // Include necessary headers
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9
10    // Constructors
11    TreeNode() : val(0), left(nullptr), right(nullptr) {}
12    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14};
15
16class Solution {
17public:
18    // Function to find the level that has the maximum sum in a binary tree.
19    int maxLevelSum(TreeNode* root) {
20        // Using a queue to perform level order traversal
21        std::queue<TreeNode*> nodeQueue{ {root} };
22      
23        int maxSum = INT_MIN;  // Initialize maxSum to the smallest possible integer
24        int resultLevel = 0;   // The level with the max sum
25        int currentLevel = 0;  // Current level during level order traversal
26      
27        // Continue while there are nodes in the queue
28        while (!nodeQueue.empty()) {
29            ++currentLevel;  // Increment level counter
30            int levelSum = 0;  // Sum of nodes at the current level
31          
32            // Process all nodes of the current level
33            for (int remaining = nodeQueue.size(); remaining > 0; --remaining) {
34                TreeNode* currentNode = nodeQueue.front();  // Get the next node
35                nodeQueue.pop();  // Remove the node from the queue
36                levelSum += currentNode->val;  // Update the level's sum
37              
38                // Add child nodes to the queue for the next level
39                if (currentNode->left) nodeQueue.push(currentNode->left);
40                if (currentNode->right) nodeQueue.push(currentNode->right);
41            }
42          
43            // Update the max sum and result level
44            if (maxSum < levelSum) {
45                maxSum = levelSum;
46                resultLevel = currentLevel;
47            }
48        }
49      
50        // Return the level with the max sum
51        return resultLevel;
52    }
53};
54
1// Definition for a binary tree node.
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8/**
9 * Calculates the maximum level sum of a binary tree.
10 * @param {TreeNode | null} root - The root node of the binary tree.
11 * @returns {number} The level (1-indexed) with the maximum sum.
12 */
13function maxLevelSum(root: TreeNode | null): number {
14    // Queue to hold nodes to visit using breadth-first search
15    const queue: (TreeNode | null)[] = [root];
16    // Variable to store the level with the maximum sum
17    let maximumLevel = 1;
18    // Variable to keep track of the current maximum sum
19    let maximumSum = Number.NEGATIVE_INFINITY;
20    // Height starts at 1, as levels are 1-indexed
21    let height = 1;
22
23    // Loop until the queue is empty
24    while (queue.length !== 0) {
25        // Get the number of nodes in the current level
26        let levelSize = queue.length;
27        // Initialize sum for the current level
28        let levelSum = 0;
29
30        // Process all nodes for the current level
31        for (let i = 0; i < levelSize; i++) {
32            // Remove the first node from the queue
33            const node = queue.shift();
34            if (node) {
35                // Add the node's value to the level sum
36                levelSum += node.val;
37                // If the left child exists, add it to the queue
38                if (node.left) queue.push(node.left);
39                // If the right child exists, add it to the queue
40                if (node.right) queue.push(node.right);
41            }
42        }
43
44        // Check if the current level has the maximum sum so far
45        if (levelSum > maximumSum) {
46            // Update the maximum sum and the corresponding level
47            maximumSum = levelSum;
48            maximumLevel = height;
49        }
50        // Move to the next level
51        height++;
52    }
53
54    // Return the level that has the maximum sum
55    return maximumLevel;
56}
57
Not Sure What to Study? Take the 2-min Quiz๏ผš

A heap is a ...?

Time and Space Complexity

The given code block is designed to find the level of a binary tree that has the maximum sum of values of its nodes.

Time complexity

The time complexity of the code can be determined by analyzing the operations performed for each node in the tree:

  • The while loop will run once for each level of the tree.
  • Inside this loop, a for loop iterates through all nodes at the current level. Since each node is visited exactly once during the BFS traversal, all the nodes in the tree will be accounted for.

Thus, if there are N nodes in the tree, the code has a time complexity of O(N) as each node is processed once.

Space complexity

The space complexity is dependent on the storage used throughout the algorithm:

  • The queue q holds the nodes at the current level being processed. In the worst case, this is equal to the maximum width of the tree, which occurs at the level with the most nodes.
  • The maximum number of nodes at any level of a binary tree could be up to N/2 (in a complete binary tree).

Therefore, the space complexity is O(N) in the worst case, because of the queue.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ