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 Breadth First Search Algorithm to Get Max Level Sum
We can traverse the binary tree using Breadth First Search Algorithm (BFS). By expanding all nodes in the current queue, we get the nodes in the next level – thus we can just sum them and store them in a dictionary by key-value pair where key is the level and value is the sum.
The python code implements the BFS algorithm to compute the sum for each 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 | # 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 q = deque([root]) ans = {} lvl = 1 while q: sz = len(q) s = 0 for _ in range(sz): x = q.popleft() s += x.val if x.left: q.append(x.left) if x.right: q.append(x.right) ans[lvl] = s lvl += 1 return max(ans.items(), key=lambda i: i[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
q = deque([root])
ans = {}
lvl = 1
while q:
sz = len(q)
s = 0
for _ in range(sz):
x = q.popleft()
s += x.val
if x.left:
q.append(x.left)
if x.right:
q.append(x.right)
ans[lvl] = s
lvl += 1
return max(ans.items(), key=lambda i: i[1])[0]We don’t need to store all the sum for each level, instead, we just need to store the maximum level and its sum. Thus the following removes the dictionary:
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 | # 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 q = deque([root]) maxLvl = maxSum = -float("inf") lvl = 1 while q: sz = len(q) s = 0 for _ in range(sz): x = q.popleft() s += x.val if x.left: q.append(x.left) if x.right: q.append(x.right) if s > maxSum: maxSum = s maxLvl = lvl lvl += 1 return maxLvl |
# 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
q = deque([root])
maxLvl = maxSum = -float("inf")
lvl = 1
while q:
sz = len(q)
s = 0
for _ in range(sz):
x = q.popleft()
s += x.val
if x.left:
q.append(x.left)
if x.right:
q.append(x.right)
if s > maxSum:
maxSum = s
maxLvl = lvl
lvl += 1
return maxLvl Both algorithms have time complexity O(N) where N is the number of nodes in the binary tree and space complexity is O(N) as we are using the deque to implement the BFS algorithm.
See also: How to Get the Maximum Level Sum of a Binary Tree using Breadth First Search Algorithm?
We can also use Depth First Search Algorithm to get the level with the maximum sum for a binary tree: Teaching Kids Programming – Maximum Level Sum of a Binary Tree using DFS Algorithm
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Dynamic Programming Algorithm to Count Contiguous Arithmetic Sequences
Next Post: Counting Algorithms to Compute All Sublists Sum
