0135MediumTreeDepth-First SearchBreadth-First SearchBinary Tree

Tier Edge Relays

Tracked in this browser only

Trains the technique from

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 network is wired as a binary tree of relays. Every relay may feed a left downstream relay and a right downstream relay, and relays at the same distance from the source form one tier. On each tier, the relay drawn furthest to the right is the one that reports that tier's health, so operations needs the reporting relay of every tier, from the source tier downward.

The tree arrives as network, a level-order listing: network[0] is the source relay's value, and the remaining entries give, tier by tier and left to right, the left feed then the right feed of each relay already listed. A null entry means that feed is absent; an absent feed contributes no entries of its own, and trailing null entries are omitted. An empty list means the network has no relays.

Return the values of the reporting relays, ordered from the source tier down to the deepest tier. Return an empty list when the network is empty. Note that a tier's rightmost relay need not descend from the previous tier's rightmost relay.

Examples

Example 1

Input: network = [8, 3, 11, null, 6, null, 14]
Output: [8, 11, 14]

The source reports its own tier. On the middle tier the right feed 11 sits furthest right, and on the bottom tier only 6 and 14 exist, so 14 reports.

Example 2

Input: network = [7, null, 4, 9, 2]
Output: [7, 4, 2]

The source has no left feed, so tier two holds only 4, whose two feeds 9 and 2 form tier three and 2 reports it.

Example 3

Input: network = [13, -7, 21, 4, -2, null, 30, null, null, 11]
Output: [13, 21, 30, 11]

Relay 21 has no left feed, so tier three is -2, 30 and the deepest tier is fed from the left branch alone, which makes 11 that tier's reporter.

Constraints

The number of relays is in the range [0, 100]
-100 <= network[i] <= 100 for every non-null entry
network is a valid level-order listing of a binary tree

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 tier_edge_relays(network: list) -> list[int]:

Java

public List<Integer> tierEdgeRelays(Integer[] network)

The intended approach

Time O(n)Space O(n)

Rebuild the tree from the listing by consuming two entries per relay in the order the relays were discovered, which mirrors how the listing was produced. Then sweep the tree one tier at a time, recording the last relay of the current tier before expanding it into the next. Sweeping by tier is what makes a rightmost relay that hangs off a left branch still get picked up.

Pythonentry point: tier_edge_relays

def tier_edge_relays(network):
    if not network or network[0] is None:
        return []
    # rebuild the tree from the level-order listing; a node is [value, left, right]
    root = [network[0], None, None]
    order = [root]
    head = 0
    cursor = 1
    while head < len(order) and cursor < len(network):
        node = order[head]
        head += 1
        for child in (1, 2):
            if cursor >= len(network):
                break
            value = network[cursor]
            cursor += 1
            if value is not None:
                node[child] = [value, None, None]
                order.append(node[child])
    edges = []
    tier = [root]
    while tier:
        edges.append(tier[-1][0])
        nxt = []
        for node in tier:
            if node[1] is not None:
                nxt.append(node[1])
            if node[2] is not None:
                nxt.append(node[2])
        tier = nxt
    return edges

The obvious version

Never builds tiers. Each relay is tagged with its depth and with the slot number it would occupy in a completely filled tree; the relay holding the largest slot number at a depth is that tier's rightmost one, so a single pass plus a per-depth maximum answers the question.

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 bf_tier_edge_relays(network):
    from collections import deque
    if not network or network[0] is None:
        return []
    # walk the listing while carrying each relay's depth and its slot number in a
    # fully filled tree; the widest slot at a depth is the rightmost relay there
    best = {}
    queue = deque([(0, 1, network[0])])
    cursor = 1
    while queue:
        depth, slot, value = queue.popleft()
        if depth not in best or slot > best[depth][0]:
            best[depth] = (slot, value)
        for child_slot in (2 * slot, 2 * slot + 1):
            if cursor >= len(network):
                continue
            child = network[cursor]
            cursor += 1
            if child is not None:
                queue.append((depth + 1, child_slot, child))
    return [best[depth][1] for depth in range(len(best))]

How this problem was checked

Reference solution executed against 10 test cases — 10 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