AlgoMaster Logo

Time Needed to Inform All Employees

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We have a company organized as a tree. The head of the company sits at the root, and every other employee has exactly one direct manager. When the head learns urgent news, they start a chain: the head tells all their direct reports (this takes informTime[headID] minutes), then each of those reports simultaneously tells their own direct reports, and so on.

Information flows in parallel down the tree. If the head has three direct reports and it takes 10 minutes to inform them, all three start spreading the news at minute 10 simultaneously. We are not summing all inform times across the whole tree. We are looking for the longest path from root to any leaf, where the "length" of each edge is the inform time of the parent node.

The problem reduces to finding the maximum root-to-leaf path sum in a tree, where each node contributes its own informTime value to every path passing through it.

Key Constraints:

  • 1 <= n <= 10^5 → An approach that recomputes a full path for each employee risks O(n^2), around 10^10 operations at the upper bound. A linear traversal that visits each node once is the target.
  • 0 <= informTime[i] <= 1000 → Inform times are non-negative, so cumulative time only increases along a path. The maximum cumulative time is at most 10^5 * 1000 = 10^8, which fits comfortably in a 32-bit signed integer.
  • informTime[i] == 0 if employee i has no subordinates → Leaf nodes contribute zero time, so the cumulative time at a leaf equals the full path sum down to that leaf.

Approach 1: Brute Force - Trace Each Employee's Path to Root

Intuition

For each employee, walk up the manager chain to the head, summing the inform times along the way. That sum is how long that employee waits to hear the news. The answer is the maximum sum across all employees.

This is the question "how long until you hear the news?" asked for every employee independently. The employee who waits the longest determines the total time.

It returns the correct answer but repeats work. If employees 5 and 7 both report to employee 3, the path from 3 up to the head is traced twice, once for each of them. The deeper a manager sits, the more times its segment of the path gets re-summed.

Algorithm

  1. For each employee i from 0 to n-1, trace the path from i back to the head using the manager array.
  2. At each step, add the inform time of the current manager to the running total.
  3. Track the maximum total time across all employees.
  4. Return the maximum.

Example Walkthrough

We trace n=8, headID=0, manager=[-1,0,0,0,1,1,2,2], informTime=[4,3,2,0,0,0,0,0]. Employee 0 is the head with inform time 4. Its reports are 1, 2, 3. Employees 4 and 5 report to 1, and 6 and 7 report to 2.

1Employee 4: walk up. 4→mgr=1 (add informTime[1]=3), 1→mgr=0 (add informTime[0]=4). 0 is head. total=7
0
-1
head +4
1
0
+3
2
0
3
0
4
1
emp 4
5
1
6
2
7
2
1/6

Code

The repeated work comes from tracing paths bottom-up. Traversing top-down instead, pushing cumulative time to each child, visits every employee exactly once.

Approach 2: DFS (Top-Down)

Intuition

Reverse the direction of Approach 1. Start at the head and push information downward, matching the actual flow of news. When we reach a node, the cumulative time to reach it is already known. We add that node's inform time and pass the new total to each child, because that many minutes pass before any child receives the news. At a leaf, the cumulative time is the full root-to-leaf path sum. Children of different parents receive the news in parallel, so the answer is the maximum cumulative time across all leaves.

The input gives a manager array rather than an adjacency list, so we build the parent-to-children mapping first, then run DFS from the head. Each node is visited once, removing the repeated path tracing from Approach 1.

Algorithm

  1. Build an adjacency list: for each employee, add them as a child of manager[i].
  2. Start DFS from headID with cumulative time 0.
  3. At each node, compute newTime = cumulativeTime + informTime[node].
  4. Recurse into each child, passing newTime.
  5. If the node has no children (it is a leaf), return the cumulative time as-is.
  6. Return the maximum time across all recursive calls.

Example Walkthrough

We use the same input as Approach 1: headID=0, manager=[-1,0,0,0,1,1,2,2], informTime=[4,3,2,0,0,0,0,0]. The DFS pushes the cumulative time down and returns the largest leaf value back up.

1Build tree. Head=0 with children [1,2,3]; 1 has [4,5]; 2 has [6,7]; 3 is a leaf
0head1234567
1/7

Code

The recursion stack grows with the tree's height, so a skewed chain of 10^5 nodes can overflow it. An iterative traversal with an explicit queue keeps the same O(n) time without using the call stack.

Approach 3: BFS (Top-Down)

Intuition

BFS computes the same per-node cumulative times as the DFS but uses a queue instead of recursion. Each queue entry carries a node ID and the cumulative time to reach that node. When we dequeue a node, we record its cumulative time as a candidate answer, add its inform time, and enqueue every child with the updated total. Since the cumulative time is highest at the leaves and every node passes through the queue, taking the maximum over all dequeued values yields the longest path.

The queue lives on the heap, so this handles a skewed tree of any depth without risking a stack overflow.

Algorithm

  1. Build an adjacency list from the manager array (same as Approach 2).
  2. Initialize a queue with (headID, 0) representing the head node with 0 cumulative time.
  3. Initialize maxTime = 0.
  4. While the queue is not empty:
    • Dequeue (node, cumulative).
    • Update maxTime = max(maxTime, cumulative).
    • Compute newTime = cumulative + informTime[node].
    • Enqueue all children of node with newTime.
  5. Return maxTime.

Example Walkthrough

1Start BFS from head (6). Queue: [(6, 0)]
0123456head
1/6

Code