0806EasyTreeDepth-First SearchBreadth-First SearchBinary Tree

Single Channel Relay Network

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 operator runs a relay network shaped as a binary tree. One relay sits at the head of the network, and every relay feeds up to two relays below it, a first branch and a second branch, either of which may be empty. Each relay is tuned to a channel, written as a number.

The network arrives as channels, a level-order listing. The first entry is the channel of the relay at the head. After that, the listing gives the first branch then the second branch of each relay already listed, in the order those relays appear, writing null wherever a branch is empty. Slots below a null are never written down, and the trailing run of null entries is left off.

The network is easiest to maintain when it runs on one channel throughout. Return true when every relay in the network is tuned to the same channel, and false otherwise.

Examples

Example 1

Input: channels = [6, 6, 6, null, 6]
Output: true

The listing names four relays and every one of them sits on channel 6. The `null` is the empty first branch below the relay listed second, not a relay.

Example 2

Input: channels = [3, 3, null, 3, null, 3, null, 9]
Output: false

Each relay here feeds exactly one relay below it, giving a chain of channels 3, 3, 3, 3 and 9. The relay at the far end of the chain is on channel 9, which is not the channel at the head.

Example 3

Input: channels = [8]
Output: true

The network is a single relay on channel 8, and it agrees with itself.

Constraints

The number of relays in the network is in the range [1, 100].
1 <= channels.length <= 200
0 <= channels[i] <= 99
An entry of channels that is null marks an empty branch rather than a relay.
channels[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 is_single_channel(channels: list[int | None]) -> bool:

Java

public boolean isSingleChannel(Integer[] channels)

The intended approach

Time O(m) for a listing of m slots: one sweep to wire the tables, then at most one visit per relay.Space O(m) for the index tables, plus O(h) for the stack on a network of depth h.

A queue sweep turns the listing into first-branch and second-branch index tables. The network runs on one channel exactly when no relay disagrees with the head relay, so hold the head's channel and visit every relay once, driving the sweep from an explicit stack and bailing out at the first disagreement. Empty branches are skipped because only wired indices are ever pushed.

Pythonentry point: is_single_channel

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 is_single_channel(channels):
    # Wire the listing into index tables, then sweep every relay from an explicit stack
    # and compare its channel with the one at the head of the network. A chain of a
    # hundred relays is therefore no deeper for the interpreter than a single relay.
    # Time O(m) for a listing of m slots, space O(m) for the tables plus O(h) stack.
    values, left, right = _decode(channels)
    tuned = values[0]
    stack = [0]
    while stack:
        here = stack.pop()
        if values[here] != tuned:
            return False
        for table in (left, right):
            kid = table[here]
            if kid != -1:
                stack.append(kid)
    return True

The obvious version

Read the listing depth by depth instead of wiring any branch links: each relay at one depth owns two consecutive slots of the next. Collect every channel found into a set and check that the set ended up with exactly one member.

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_is_single_channel(channels):
    seen = set()
    for row in _levels(channels):
        for channel in row:
            seen.add(channel)
    return len(seen) == 1

How this problem was checked

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