Binary Tree Right Side View
Real-world version: Tier Edge RelaysThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def tier_edge_relays(network: list) -> list[int]:public List<Integer> tierEdgeRelays(Integer[] network)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 10 test cases: 10 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's