DDSA Solutions

2583. Kth Largest Sum in a Binary Tree

MediumView on LeetCode
TreeBreadth-First SearchSortingBinary TreeHeap (Priority Queue)
Time: O(n log n)
Space: O(n)

Problem Overview

Kth largest sum of binary tree levels.

Intuition

Kth largest sum of binary tree levels. BFS to get each level sum, sort descending, return kth.

Algorithm

  1. 1BFS, compute sum per level. Sort descending. Return sums[k-1].

Common Pitfalls

  • •If fewer than k levels: return -1. Use BFS for clean level-order traversal.
2583.cs
C#
// Approach: BFS collects row sums; sort descending and return kth element.
// Time: O(n log n) Space: O(n)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public long KthLargestLevelSum(TreeNode root, int k)
    {
        List<long> levelSums = new List<long>();
        Dfs(root, 0, levelSums);
        if (levelSums.Count < k)
            return -1;

        levelSums.Sort((a, b) => b.CompareTo(a));
        return levelSums[k - 1];
    }

    private void Dfs(TreeNode root, int level, List<long> levelSums)
    {
        if (root == null)
            return;
        if (levelSums.Count == level)
            levelSums.Add(0);
        levelSums[level] += root.val;
        Dfs(root.left, level + 1, levelSums);
        Dfs(root.right, level + 1, levelSums);
    }
}
Was this solution helpful?

Related Problems