DEV Community

Ankan Bhattacharya
Ankan Bhattacharya

Posted on • Edited on

Max Level Sum of A Binary Tree

Problem Statement:
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.

Approach

This was a problem which had some quite interesting solving... In this approach I used a BFS. I took one row at a time found its sum and compared it with the previous sum. If its greater than the previous one then I replaced the max Level with the current Level. Finally at the end of the looping I returned the max Level.

Algo Images

Image description

Image description

Code

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 root == None: return None

        currentLevel: int = 1
        maxLevel: int = None
        maxSum: int = None

        BFSQueue: list[TreeNode] = [root]

        while len(BFSQueue) > 0:
            currentLength: int = len(BFSQueue)
            currentSum: int = 0

            for i in range(currentLength):
                currentNode: TreeNode = BFSQueue.pop(0)
                currentSum += currentNode.val

                if currentNode.left != None: BFSQueue.append(currentNode.left)
                if currentNode.right != None: BFSQueue.append(currentNode.right)

            if (maxSum == None) or (maxSum < currentSum):
                maxSum = currentSum
                maxLevel = currentLevel

            currentLevel += 1

        return maxLevel
Enter fullscreen mode Exit fullscreen mode

Result Image

Image description

If you got to learn something from this post make sure you like the post and click on the follow button for more such content.
Also if you have some suggestions and want to improve it make sure you comment down below...

Top comments (0)