0795MediumTreeBreadth-First SearchSortingBinary Tree

Kth Busiest Relay Tier

Tracked in this browser only

Trains the technique from

LeetCode 2583Kth Largest Sum in a Binary Tree

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def kth_largest_tier(stations: list[int | None], k: int) -> int:

Java

public long kthLargestTier(Integer[] stations, int k)

The intended approach

Time O(n + t log t) for n listed slots and t tiers, which is O(n log n) at worst: the wiring and the tier sweep are linear and only the tier loads are sorted.Space O(n) for the index tables and the tier frontiers, plus O(t) for the tier loads.

Wire the listing into left and right index tables with a queue sweep, then walk the tree one tier at a time: hold the current tier as an explicit list of station indices, add up their loads, and build the next tier from their recorded children. That keeps the walk iterative, so a tree that is one long strand cannot overflow anything. Sort the tier loads from largest downward and read off position k, first checking that the tree has that many tiers.

Pythonentry point: kth_largest_tier

def _decode(listing):
    """Compact level-order listing -> (values, left, right) index tables."""
    if not listing or listing[0] is None:
        return [], [], []
    left = [-1] * len(listing)
    right = [-1] * len(listing)
    queue = [0]
    head = 0
    slot = 1
    while head < len(queue) and slot < len(listing):
        here = queue[head]
        head += 1
        if slot < len(listing):
            if listing[slot] is not None:
                left[here] = slot
                queue.append(slot)
            slot += 1
        if slot < len(listing):
            if listing[slot] is not None:
                right[here] = slot
                queue.append(slot)
            slot += 1
    return list(listing), left, right


def _encode(values, left, right):
    """(values, left, right) index tables -> compact level-order listing."""
    if not values:
        return []
    out = [values[0]]
    order = [0]
    head = 0
    while head < len(order):
        here = order[head]
        head += 1
        for table in (left, right):
            kid = table[here]
            if kid == -1:
                out.append(None)
            else:
                out.append(values[kid])
                order.append(kid)
    while out and out[-1] is None:
        out.pop()
    return out

def kth_largest_tier(stations, k):
    values, left, right = _decode(stations)
    if not values:
        return -1
    # sweep tier by tier with an explicit frontier, never recursing
    totals = []
    frontier = [0]
    while frontier:
        total = 0
        nxt = []
        for here in frontier:
            total += values[here]
            for table in (left, right):
                kid = table[here]
                if kid != -1:
                    nxt.append(kid)
        totals.append(total)
        frontier = nxt
    if k > len(totals):
        return -1
    totals.sort(reverse=True)
    return totals[k - 1]

The obvious version

Read the tiers straight off the listing without ever wiring a child link: the first tier is the opening entry, and each following tier takes the next two slots for every station of the tier before it, keeping the entries that are not null. Then pull the largest total off the list k - 1 times and return the largest of what is left.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def _levels(listing):
    """Compact level-order listing -> list of value lists, one per depth."""
    if not listing or listing[0] is None:
        return []
    out = []
    here = [listing[0]]
    slot = 1
    while here:
        out.append(here)
        nxt = []
        for _ in range(2 * len(here)):
            if slot < len(listing):
                got = listing[slot]
                slot += 1
                if got is not None:
                    nxt.append(got)
        here = nxt
    return out

def bf_kth_largest_tier(stations, k):
    tiers = _levels(stations)
    if k > len(tiers):
        return -1
    totals = [sum(t) for t in tiers]
    for _ in range(k - 1):
        totals.remove(max(totals))
    return max(totals)

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in