Jobs

Interviews

Discussions

Kth Largest Sum in a Binary Tree

Medium

Asked by:

36 views

Topics:

TreesBreadth-First Search

You are given the root of a binary tree and a positive integer k.

The level sum in the tree is the sum of the values of the nodes that are on the same level.

Return the k^th largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.

Note that two nodes are on the same level if they have the same distance from the root.

Example 1:

Input: root = [5,8,9,2,1,3,7,4,6], k = 2
Output: 13
Explanation: The level sums are the following:
- Level 1: 5.
- Level 2: 8 + 9 = 17.
- Level 3: 2 + 1 + 3 + 7 = 13.
- Level 4: 4 + 6 = 10.
The 2^nd largest level sum is 13.

Example 2:

Input: root = [1,2,null,3], k = 1
Output: 3
Explanation: The largest level sum is 3.

Constraints:

The number of nodes in the tree is n.
2 <= n <= 10⁵
1 <= Node.val <= 10⁶
1 <= k <= n

Try coding it in LeetCode

Kth Largest Sum in a Binary Tree

Medium

Asked by:

36 views

Topics:

TreesBreadth-First Search

You are given the root of a binary tree and a positive integer k.

The level sum in the tree is the sum of the values of the nodes that are on the same level.

Return the k^th largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.

Note that two nodes are on the same level if they have the same distance from the root.

Example 1:

Input: root = [5,8,9,2,1,3,7,4,6], k = 2
Output: 13
Explanation: The level sums are the following:
- Level 1: 5.
- Level 2: 8 + 9 = 17.
- Level 3: 2 + 1 + 3 + 7 = 13.
- Level 4: 4 + 6 = 10.
The 2^nd largest level sum is 13.

Example 2:

Input: root = [1,2,null,3], k = 1
Output: 3
Explanation: The largest level sum is 3.

Constraints:

The number of nodes in the tree is n.
2 <= n <= 10⁵
1 <= Node.val <= 10⁶
1 <= k <= n

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the node data in the binary tree; can they be negative, zero, or floating-point numbers?
What happens if the value of 'k' is larger than the number of distinct sum values in the tree; should I return a specific value or throw an exception?
How is the binary tree structured (e.g., is it a binary search tree, a complete binary tree, or a general binary tree)?
By 'sum,' do you mean the sum of node values from the root to any node, or the sum of values from any path in the tree?
Is 'k' 1-indexed or 0-indexed?

Brute Force Solution

Approach

The brute force method finds the kth largest sum by exhaustively calculating the sum of nodes at each level in the tree. We find the sum for every level, then determine the kth largest sum among all those level sums. This approach doesn't optimize; it simply tries everything.

Here's how the algorithm would work step-by-step:

Go through the tree level by level, one level at a time.
For each level, add up the values of all the nodes present in that level.
After calculating the sum for every level in the tree, put all those level sums into a list.
Sort this list of level sums from largest to smallest.
Find the element at the kth position in the sorted list. This element represents the kth largest level sum.

Code Implementation

from collections import deque

def kth_largest_level_sum_brute_force(root, k_value):
    if not root:
        return -1

    level_sums = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level_sum = 0

        # Iterate through all nodes at the current level
        for _ in range(level_size):
            node = queue.popleft()
            current_level_sum += node.val

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

        level_sums.append(current_level_sum)

    # Need to handle the edge case where k is larger than the number of levels
    if k_value > len(level_sums):
        return -1

    # Sort level sums to easily find the kth largest sum
    level_sums.sort(reverse=True)

    return level_sums[k_value - 1]

Big(O) Analysis

Time Complexity

O(n log n) – Let n be the number of nodes in the binary tree. The level-order traversal visits each node once to calculate the sum of each level, contributing O(n). After computing level sums, we store them in a list. Sorting this list of level sums takes O(m log m) time, where m is the number of levels in the tree. Since the maximum number of levels in a binary tree with n nodes is approximately n (in the case of a skewed tree) and the minimum is log n (in the case of a balanced tree), m can be at most n. Thus, the sorting operation dominates the complexity when the tree is close to a full or complete binary tree, resulting in O(n log n) when the number of levels is proportional to n. In the worst-case skewed tree, m is proportional to n, so sorting takes O(n log n) time.

Space Complexity

O(W) – The algorithm uses a list to store the sum of nodes at each level. In the worst-case scenario, which occurs in a complete binary tree, the last level contains approximately half of the nodes. Thus, the size of this list is proportional to the width (W) of the widest level in the tree. Sorting this list in place doesn't increase auxiliary space complexity beyond storing the sums. Therefore, the space complexity is O(W), where W is the maximum width of the tree.

Optimal Solution

Approach

The key idea is to calculate the sum of values at each level of the binary tree and then find the kth largest among these sums. We can efficiently traverse the tree level by level and keep track of the sum at each level, and then find the kth largest sum.

Here's how the algorithm would work step-by-step:

First, we traverse the binary tree level by level.
As we visit each node, we identify its level in the tree.
We keep track of the sum of the node values at each level.
Once we have the sum for each level, we put those sums into a data structure that can efficiently give us the kth largest value.
Finally, we return the kth largest sum we found.

Code Implementation

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_largest_level_sum(root, k_value):
    if not root:
        return -1

    level_sums = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level_sum = 0

        # Traverse all nodes at the current level
        for _ in range(level_size):
            node = queue.popleft()
            current_level_sum += node.val

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        level_sums.append(current_level_sum)

    # Removing duplicates ensures correct Kth selection
    unique_level_sums = sorted(list(set(level_sums)), reverse=True)

    # Validate K value to avoid errors
    if k_value > len(unique_level_sums):
        return -1

    # Return kth largest sum
    return unique_level_sums[k_value - 1]

Big(O) Analysis

Time Complexity

O(n + m log m) – The level-order traversal of the binary tree visits each node once, taking O(n) time, where n is the number of nodes in the tree. Then, we have m level sums, where m is the number of levels in the tree. To find the kth largest sum among these m sums, sorting the level sums would take O(m log m) time. Therefore, the overall time complexity is dominated by the sum of the traversal and the kth largest element computation, resulting in O(n + m log m).

Space Complexity

O(W) – The algorithm uses a queue for level order traversal, which can hold up to W nodes at the widest level of the tree, where W is the maximum width of the binary tree. Additionally, it stores level sums, which in the worst case (a complete binary tree) can be up to the height of the tree (log N), but is generally bounded by W. Therefore, the dominant space usage comes from storing the nodes in the queue, resulting in a space complexity of O(W), where W is the maximum width of the tree. This space is used to keep track of the nodes during the level-by-level traversal.

Edge Cases

Case	How to Handle
Null or empty binary tree	Return an empty list immediately, as there are no sums to compute.
K is less than or equal to 0	Return an empty list or throw an IllegalArgumentException, as requesting the kth largest with k <= 0 is invalid.
K is larger than the number of levels in the tree	Return the sums of all levels in descending order, as there aren't enough levels to return the Kth largest.
Binary tree with a single node	Return a list containing only the root's value if k is 1, otherwise return an empty list if k > 1.
Binary tree with all nodes having negative values	The solution should correctly handle negative sums, producing a list of sums that may all be negative.
Binary tree with large depth leading to potential integer overflow in sum	Use a data type with a larger range like `long` to store the sum of each level to prevent overflow.
Skewed binary tree (e.g., linked list)	The solution should still correctly calculate level sums, although performance might degrade to O(n) where n is the number of nodes due to the tree structure.
Binary tree with duplicate node values across multiple levels	The level-order traversal should correctly sum the values at each level regardless of duplicate node values.

Null or empty binary tree

How to Handle:

Return an empty list immediately, as there are no sums to compute.

K is less than or equal to 0

How to Handle:

Return an empty list or throw an IllegalArgumentException, as requesting the kth largest with k <= 0 is invalid.

K is larger than the number of levels in the tree

How to Handle:

Return the sums of all levels in descending order, as there aren't enough levels to return the Kth largest.

Binary tree with a single node

How to Handle:

Return a list containing only the root's value if k is 1, otherwise return an empty list if k > 1.

Binary tree with all nodes having negative values

How to Handle:

The solution should correctly handle negative sums, producing a list of sums that may all be negative.

Binary tree with large depth leading to potential integer overflow in sum

How to Handle:

Use a data type with a larger range like `long` to store the sum of each level to prevent overflow.

Skewed binary tree (e.g., linked list)

How to Handle:

The solution should still correctly calculate level sums, although performance might degrade to O(n) where n is the number of nodes due to the tree structure.

Binary tree with duplicate node values across multiple levels

How to Handle:

The level-order traversal should correctly sum the values at each level regardless of duplicate node values.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the node data in the binary tree; can they be negative, zero, or floating-point numbers?
What happens if the value of 'k' is larger than the number of distinct sum values in the tree; should I return a specific value or throw an exception?
How is the binary tree structured (e.g., is it a binary search tree, a complete binary tree, or a general binary tree)?
By 'sum,' do you mean the sum of node values from the root to any node, or the sum of values from any path in the tree?
Is 'k' 1-indexed or 0-indexed?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Go through the tree level by level, one level at a time.
For each level, add up the values of all the nodes present in that level.
After calculating the sum for every level in the tree, put all those level sums into a list.
Sort this list of level sums from largest to smallest.
Find the element at the kth position in the sorted list. This element represents the kth largest level sum.

Code Implementation

from collections import deque

def kth_largest_level_sum_brute_force(root, k_value):
    if not root:
        return -1

    level_sums = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level_sum = 0

        # Iterate through all nodes at the current level
        for _ in range(level_size):
            node = queue.popleft()
            current_level_sum += node.val

            if node.left:
                queue.append(node.left)

            if node.right:
                queue.append(node.right)

        level_sums.append(current_level_sum)

    # Need to handle the edge case where k is larger than the number of levels
    if k_value > len(level_sums):
        return -1

    # Sort level sums to easily find the kth largest sum
    level_sums.sort(reverse=True)

    return level_sums[k_value - 1]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, we traverse the binary tree level by level.
As we visit each node, we identify its level in the tree.
We keep track of the sum of the node values at each level.
Once we have the sum for each level, we put those sums into a data structure that can efficiently give us the kth largest value.
Finally, we return the kth largest sum we found.

Code Implementation

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_largest_level_sum(root, k_value):
    if not root:
        return -1

    level_sums = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level_sum = 0

        # Traverse all nodes at the current level
        for _ in range(level_size):
            node = queue.popleft()
            current_level_sum += node.val

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        level_sums.append(current_level_sum)

    # Removing duplicates ensures correct Kth selection
    unique_level_sums = sorted(list(set(level_sums)), reverse=True)

    # Validate K value to avoid errors
    if k_value > len(unique_level_sums):
        return -1

    # Return kth largest sum
    return unique_level_sums[k_value - 1]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty binary tree	Return an empty list immediately, as there are no sums to compute.
K is less than or equal to 0	Return an empty list or throw an IllegalArgumentException, as requesting the kth largest with k <= 0 is invalid.
K is larger than the number of levels in the tree	Return the sums of all levels in descending order, as there aren't enough levels to return the Kth largest.
Binary tree with a single node	Return a list containing only the root's value if k is 1, otherwise return an empty list if k > 1.
Binary tree with all nodes having negative values	The solution should correctly handle negative sums, producing a list of sums that may all be negative.
Binary tree with large depth leading to potential integer overflow in sum	Use a data type with a larger range like `long` to store the sum of each level to prevent overflow.
Skewed binary tree (e.g., linked list)	The solution should still correctly calculate level sums, although performance might degrade to O(n) where n is the number of nodes due to the tree structure.
Binary tree with duplicate node values across multiple levels	The level-order traversal should correctly sum the values at each level regardless of duplicate node values.

Null or empty binary tree

How to Handle:

Return an empty list immediately, as there are no sums to compute.

K is less than or equal to 0

How to Handle:

Return an empty list or throw an IllegalArgumentException, as requesting the kth largest with k <= 0 is invalid.

K is larger than the number of levels in the tree

How to Handle:

Return the sums of all levels in descending order, as there aren't enough levels to return the Kth largest.

Binary tree with a single node

How to Handle:

Return a list containing only the root's value if k is 1, otherwise return an empty list if k > 1.

Binary tree with all nodes having negative values

How to Handle:

The solution should correctly handle negative sums, producing a list of sums that may all be negative.

Binary tree with large depth leading to potential integer overflow in sum

How to Handle:

Use a data type with a larger range like `long` to store the sum of each level to prevent overflow.

Skewed binary tree (e.g., linked list)

How to Handle:

The solution should still correctly calculate level sums, although performance might degrade to O(n) where n is the number of nodes due to the tree structure.

Binary tree with duplicate node values across multiple levels

How to Handle:

The level-order traversal should correctly sum the values at each level regardless of duplicate node values.