Teaching Kids Programming – Maximum Level Sum of a Binary Tree using DFS Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Using Depth First Search Algorithm to Get Max Level Sum

We can solve this problem using Breadth First Search Algorithm: Counting Algorithms to Compute All Sublists Sum.

We can also use the Depth First Search Algorithm to solve this. By traversing the binary tree using Depth First Search, we pass down the level of the node and we accumulate the sum for each level. Finally, we can return the key with the maximum value (sum).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        def dfs(root, lvl, sums):
            if root is None:
                return
            sums[lvl] += root.val
            dfs(root.left, lvl + 1, sums)
            dfs(root.right, lvl + 1, sums)
        sums = defaultdict(int)
        dfs(root, 1, sums)
        return max(sums.items(), key=lambda x: x[1])[0]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        if not root:
            return 0
        def dfs(root, lvl, sums):
            if root is None:
                return
            sums[lvl] += root.val
            dfs(root.left, lvl + 1, sums)
            dfs(root.right, lvl + 1, sums)
        sums = defaultdict(int)
        dfs(root, 1, sums)
        return max(sums.items(), key=lambda x: x[1])[0]

The time complexity is O(N) where N is the number of the nodes in the binary tree. The space complexity is O(N) as we are using Recursion and also the dictionary to store the key-value pairs (level and sum).

–EOF (The Ultimate Computing & Technology Blog) —