How to Get the Maximum Level Sum of a Binary Tree using Breadth First Search Algorithm?

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on. Return the smallest level X such that the sum of all the values of nodes at level X is maximal.

Example 1:
Input: [1,7,0,7,-8,null,null]
Output: 2

binary-tree

Explanation:
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Note:
The number of nodes in the given tree is between 1 and 10^4.
-10^5 <= node.val <= 10^5

Store the Sum-Level Pairs using C++ Map

The C++ map stores the keys in the ascending order – thus we can store the sum-level pairs and return the last element of the map – which will give us the level for the maximum sum.

When we do the BFS (Breadth First Search) algorithm, we iterate all nodes in the queue – which are of same level, compute the sum, and enqueue the sum-level. If a sum has appeared before, we need to keep the minimum level.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        queue<TreeNode*> Q;
        if (root == nullptr) return 0;
        Q.push(root);
        int level = 0;
        map<int, int> sum;
        while (!Q.empty()) {
            int cursum = 0;
            int count = Q.size();
            level ++;
            // expand nodes of same level
            for (int i = 0; i < count; ++ i) {
                auto p = Q.front();
                cursum += p->val;
                if (p->left != nullptr) Q.push(p->left);
                if (p->right != nullptr) Q.push(p->right);
                Q.pop();
            }
            if (sum.find(cursum) == sum.end()) {
                sum[cursum] = level;
            } else {
                sum[cursum] = min(sum[cursum], level);
            }
        }
        return rbegin(sum)->second;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        queue<TreeNode*> Q;
        if (root == nullptr) return 0;
        Q.push(root);
        int level = 0;
        map<int, int> sum;
        while (!Q.empty()) {
            int cursum = 0;
            int count = Q.size();
            level ++;
            // expand nodes of same level
            for (int i = 0; i < count; ++ i) {
                auto p = Q.front();
                cursum += p->val;
                if (p->left != nullptr) Q.push(p->left);
                if (p->right != nullptr) Q.push(p->right);
                Q.pop();
            }
            if (sum.find(cursum) == sum.end()) {
                sum[cursum] = level;
            } else {
                sum[cursum] = min(sum[cursum], level);
            }
        }
        return rbegin(sum)->second;
    }
};

The last element of a C++ std::map can get obtained via the rbegin iterator and the end is actually one element beyond the last – which may return undefined value.

The algorithmic complexity is O(NLogN) where N is the number of the binary trees – as the C++ std::map internally uses a Red/Black tree to maintain the order and it takes O(logN) to find an element.

See also: Teaching Kids Programming – Maximum Level Sum of a Binary Tree using BFS Algorithm

–EOF (The Ultimate Computing & Technology Blog) —