AlgoMaster Logo

Time Needed to Inform All Employees

Last Updated: March 28, 2026

medium
4 min read

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.

The critical insight is that 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. So we are not summing all inform times. 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.

This is essentially finding the maximum root-to-leaf path sum in a tree, where each node contributes its own informTime value to the paths passing through it.

Key Constraints:

  • 1 <= n <= 10^5 → We need O(n) or O(n log n). Any approach that recomputes paths from scratch for each employee risks O(n^2), which could be 10^10 operations at the upper bound.
  • 0 <= informTime[i] <= 1000 → Inform times are non-negative, so cumulative times only increase along a path. No need to worry about negative weights or cycles.
  • manager[headID] == -1 → There is exactly one root. The tree is guaranteed to be connected and valid.
  • informTime[i] == 0 if employee i has no subordinates → Leaf nodes contribute zero time. The last step in any path is always free.

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

Intuition

The most straightforward idea: for each employee, walk up the manager chain all the way to the head, summing up the inform times along the way. The answer is the maximum sum across all employees.

Think of it like asking every employee "how long until you hear the news?" Each employee can figure this out by looking at their manager, their manager's manager, and so on up to the head, adding up all the inform times along the way. The employee who waits the longest determines the answer.

This works correctly, but it is doing redundant work. If employees 5 and 7 both report to employee 3, we trace the path from 3 up to the head twice, once for each of them.

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

1Employee 0: trace path to head. 0→mgr[0]=2 (head). Time = informTime[2]=1
0
2
emp 0
1
2
2
-1
head
3
2
4
2
5
2
1/4

Code

This approach works but traces overlapping paths repeatedly. What if we traversed from the top down instead, pushing cumulative time to each child so every employee is visited exactly once?

Approach 2: DFS (Top-Down)

Intuition

Instead of each employee looking upward, flip the direction. Start at the head and push information downward, just like the actual flow of news. When we visit a node, we already know how much time has elapsed to reach it. We add that node's inform time and pass the new total to each child. At leaf nodes, the cumulative time represents a complete root-to-leaf path. The answer is the maximum across all leaves.

We build the tree first (since we are given a manager array, not an adjacency list), then run DFS from the head. Each node is visited exactly once, eliminating all the redundant 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

1Build tree from manager array. Head=2 with children [0,1,3,4,5]
012head345
1/6

Code

The recursive DFS can hit a stack overflow on extremely deep trees. Can we achieve the same O(n) time with an iterative approach?

Approach 3: BFS (Top-Down)

Intuition

The BFS approach is conceptually identical to DFS but uses a queue instead of recursion. We process the tree node by node in FIFO order. Each entry in the queue carries the node ID and the cumulative time to reach that node. When we dequeue a node, we add its inform time and enqueue all its children with the updated cumulative time.

This approach is particularly useful when the tree is very deep (skewed), because BFS uses a queue on the heap instead of relying on the call stack.

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:

a. Dequeue (node, cumulative).

b. Update maxTime = max(maxTime, cumulative).

c. Compute newTime = cumulative + informTime[node].

d. Enqueue all children of node with newTime.

  1. Return maxTime.

Example Walkthrough

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

Code