We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Level of Tree with Minimum Sum

Number: 3467

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given the root of a binary tree where each node contains an integer value, return the level of the tree that has the minimum sum of node values. The tree levels start at 1 for the root, and the level of any other node is its distance from the root plus one. In the event of a tie (multiple levels with the same sum), return the lowest level number.

Key Insights

  • Use a Breadth-First Search (BFS) to traverse the tree level by level.
  • At each level, calculate the sum of node values.
  • Keep track of the minimum sum encountered and the corresponding level.
  • Since levels are processed sequentially from root downwards, in case of ties the first encountered (lowest) level with that sum is used.
  • The constraints allow for up to 10^5 nodes, so an O(n) solution using BFS is efficient.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes, as every node is processed exactly once. Space Complexity: O(n) in the worst case if the tree is highly unbalanced (or for the maximum number of nodes stored in the BFS queue).

Solution

The solution uses a BFS approach to traverse the tree level by level. We initialize a queue with the root node and process nodes in batches corresponding to each level. For every level, we:

  • Compute the sum of the nodes.
  • Update the minimum sum and record the level if this sum is lower than the current minimum.
  • Enqueue the left and right children (if any) of the nodes in the current level. This method ensures that we only use additional space proportional to the maximum number of nodes at any level and that we correctly identify the level with the minimum sum.

Code Solutions

# 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 minLevelSum(self, root: TreeNode) -> int:
        from collections import deque
        
        # Create a queue for BFS with the initial root node.
        queue = deque([root])
        current_level = 1
        min_sum = float("inf")
        min_level = 1

        # Process each level of the tree.
        while queue:
            level_sum = 0
            level_size = len(queue)
            
            # Process all nodes in the current level.
            for _ in range(level_size):
                node = queue.popleft()
                level_sum += node.val
                
                # Enqueue left child if available.
                if node.left:
                    queue.append(node.left)
                # Enqueue right child if available.
                if node.right:
                    queue.append(node.right)
            
            # Update minimum sum and level if a new minimum is found.
            if level_sum < min_sum:
                min_sum = level_sum
                min_level = current_level
            
            current_level += 1
        
        return min_level
← Back to All Questions