Show problems as
Classic problem #2385MediumHash TableTreeDepth-First SearchBreadth-First SearchBinary Tree

Amount of Time for Binary Tree to Be Infected

Real-world version: Firmware Cascade Minutes
Tracked in this browser only
Read Amount of Time for Binary Tree to Be Infected on LeetCode(opens in a new tab)

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

A rack of relays is wired as a binary tree. The wiring arrives as layout, the level-order walk of that tree: layout[0] is the root relay, and the walk then lists the left and right child slot of every relay it has already listed, in the same order, writing null for a slot with no relay in it. A null slot has no child slots of its own, and trailing null entries are left off the end. Every relay carries a different label.

A firmware update is loaded onto the relay labelled seed. Each wire joins a relay to a child and carries the update in either direction. During one minute, every relay that already holds the update pushes it across all of its wires, so each neighbouring relay without the update picks it up.

Return the number of minutes until every relay in the rack holds the update. A rack of one relay is already done, so the answer is 0.

Examples

Example 1

Input
layout = [4,2,9,1,3,null,7], seed = 2
Output
3

Minute 1 puts the update on relays 1, 3 and 4. Minute 2 puts it on relay 9, and minute 3 puts it on relay 7, which is the last relay in the rack.

Example 2

Input
layout = [8,3,10,1,6,null,14,null,null,4,7,13], seed = 6
Output
5

The update spreads to relays 3, 4 and 7 in minute 1, to 1 and 8 in minute 2, to 10 in minute 3, to 14 in minute 4 and to 13 in minute 5.

Constraints

  • The number of relays in the rack is in the range [1, 10^5].
  • 1 <= relay label <= 10^5
  • Every relay carries a different label.
  • layout is the level-order walk of the tree, with null for an empty child slot and trailing nulls omitted.
  • seed is the label of a relay that is present in the rack.

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 cascade_minutes(layout: list[int | None], seed: int) -> int:
Java
public int cascadeMinutes(Integer[] layout, int seed)

More on the same topics