Show problems as
Classic problem #2583MediumTreeBreadth-First SearchSortingBinary Tree

Kth Largest Sum in a Binary Tree

Real-world version: Kth Busiest Relay Tier
Tracked in this browser only
Read Kth Largest Sum in a Binary Tree on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A broadcast tower feeds a tree of relay stations. Each station passes traffic down to at most two stations, one on its left and one on its right, and every station carries a whole number of load units.

The tree arrives as stations, a level-order listing. The first entry is the load of the top station. After that the listing gives the left then the right station below each station already listed, in the order those stations appear, writing null where no station hangs on that side. Slots below a null are never written down.

A tier is the group of stations lying the same number of hops below the top station: the first tier is the top station on its own, the second tier is the stations it feeds, and so on. The load of a tier is the sum of the loads of the stations in it.

Return the k-th largest tier load. Two tiers carrying the same load are counted separately, so a repeated load takes up as many ranks as it has tiers. If the tree has fewer than k tiers, return -1.

Examples

Example 1

Input
stations = [8, 3, 5, 1, 9, null, 2, 4], k = 2
Output
8

The tiers hold loads 8, then 3 and 5, then 1, 9 and 2, then 4, so the tier loads are 8, 8, 12 and 4. Ranked from largest they read 12, 8, 8, 4, and the second of those is 8.

Example 2

Input
stations = [1, null, 2, null, 3, 4, 5], k = 1
Output
9

Station 1 feeds only on its right, and so does station 2, so the tiers are 1, then 2, then 3, then 4 and 5 together. The tier loads are 1, 2, 3 and 9, and the largest is 9.

Example 3

Input
stations = [7, 2, 3], k = 4
Output
-1

The tree has only two tiers, carrying 7 and 5, so there is no fourth rank.

Constraints

  • The number of stations in the tree is in the range [2, 10^5].
  • 1 <= stations[i] <= 10^6
  • An entry of stations that is null marks an absent station rather than a load
  • 1 <= k <= 10^5
  • k is at most the number of stations in the tree
  • stations[0] is never null

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def kth_largest_tier(stations: list[int | None], k: int) -> int:
Java
public long kthLargestTier(Integer[] stations, int k)

More on the same topics