Card 05/ 08
Tree Patterns Example: Who Hears the News in Each Minute of a Message Cascade
Each volunteer forwards a message to at most two others a minute after receiving it: the people reached in each minute are the tree's levels, read with a queue.
When a tree question asks about rounds, minutes or steps from the root, each round is a level of the tree, and a queue hands the levels out in order. A volunteer group passes urgent news down a phone tree: Mia hears it at minute 0, and everyone who hears it calls at most two others, who hear it a minute later. Mia calls Raj and Lou; Raj calls Ada and Ben; Lou calls Kit; Ada calls Zoe; Kit calls Tom and Uma. The coordinator wants to know who hears the news in each minute, and how long until everyone has it. The question never says level; a minute is one.
Who hears the news in minute 2?
Ada, Ben and Kit, the people two calls from Mia. Zoe, Tom and Uma hear it in minute 3, the last.
Mia, minute 0
Raj, minute 1
Ada, minute 2
Zoe, minute 3
null, no second call
Ben, minute 2
Lou, minute 1
null, no first call
Kit, minute 2
Tom, minute 3
Uma, minute 3
A breadth-first visit takes people from the front of a queue and adds the people they call at the back. The step that separates the minutes is reading the queue's size once, when the minute starts: exactly that many people are dequeued, and everyone added meanwhile waits for the next minute. The table gives the queue at the start of each minute, from the run.
| Minute | Queue when the minute starts | Size read | Added for the next minute |
|---|---|---|---|
| 0 | Mia | 1 | Raj, Lou |
| 1 | Raj, Lou | 2 | Ada, Ben, Kit |
| 2 | Ada, Ben, Kit | 3 | Zoe, Tom, Uma |
| 3 | Zoe, Tom, Uma | 3 | Nobody |
The listing prints the same rows, then groups the people a second way, by passing each call its depth.
from collections import deque
class Person:
def __init__(self, name: str, left: Person | None = None, right: Person | None = None) -> None:
self.name = name
self.left = left
self.right = right
def minutes(root: Person) -> int:
queue = deque([root])
minute = 0
while True:
size = len(queue)
heard = [person.name for person in queue]
for _ in range(size):
person = queue.popleft()
for contact in (person.left, person.right):
if contact is not None:
queue.append(contact)
added = [person.name for person in queue]
print(f"minute {minute}: queue {heard}, size {size}, adds {added}")
if not queue:
return minute
minute += 1
def levels_by_depth(person: Person | None, depth: int, levels: list[list[str]]) -> list[list[str]]:
if person is None:
return levels
if depth == len(levels):
levels.append([])
levels[depth].append(person.name)
levels_by_depth(person.left, depth + 1, levels)
levels_by_depth(person.right, depth + 1, levels)
return levels
cascade = Person("Mia",
Person("Raj", Person("Ada", Person("Zoe")), Person("Ben")),
Person("Lou", None, Person("Kit", Person("Tom"), Person("Uma"))))
print(f"everyone has the message after {minutes(cascade)} minutes")
print("by depth:", levels_by_depth(cascade, 0, []))minute 0: queue ['Mia'], size 1, adds ['Raj', 'Lou']
minute 1: queue ['Raj', 'Lou'], size 2, adds ['Ada', 'Ben', 'Kit']
minute 2: queue ['Ada', 'Ben', 'Kit'], size 3, adds ['Zoe', 'Tom', 'Uma']
minute 3: queue ['Zoe', 'Tom', 'Uma'], size 3, adds []
everyone has the message after 3 minutes
by depth: [['Mia'], ['Raj', 'Lou'], ['Ada', 'Ben', 'Kit'], ['Zoe', 'Tom', 'Uma']]Everyone has the news after 3 minutes, the number of levels less one. Passing the depth down a recursive visit groups the people by level too, as the last line shows, but it reaches Zoe before Kit, so it only knows the groups once the whole tree is done; the queue hands each minute out complete and in time order, and it has no recursion limit. Both are O(n) time; the queue holds at most one level, O(w) space for a widest level of w people.
← → move through sections and cards