Time Needed to Inform All Employees - Solution & Explanation

Problem Overview: A company has n employees with a hierarchical manager structure forming a tree. The head starts an announcement, and each manager takes informTime[i] minutes to pass the message to their direct subordinates. The goal is to compute the total time required for the information to reach every employee.

The manager array defines a parent-child relationship, which naturally forms a tree. The head of the company is the root, and every employee is a node. Solving the problem means computing the longest time taken along any path from the head to a leaf employee.

Approach 1: Depth-First Search (DFS) Traversal (O(n) time, O(n) space)

Build an adjacency list where each manager maps to their direct subordinates. Start a DFS from the head employee and propagate accumulated time down the hierarchy. Each recursive call adds the current manager's informTime to the running total before visiting children.

The key insight: the overall time equals the maximum time taken along any root-to-leaf path in the management tree. DFS naturally explores one branch fully before moving to the next, making it easy to track the longest propagation time. Use recursion or an explicit stack to traverse the tree. The traversal touches each employee exactly once, giving O(n) time complexity and O(n) space for the adjacency list and recursion stack.

This approach works well when you're comfortable modeling hierarchical relationships as trees and computing path-based metrics. DFS keeps the implementation compact and maps directly to the recursive structure of the organization chart.

Approach 2: Breadth-First Search (BFS) Level Traversal (O(n) time, O(n) space)

Another way to model the spread of information is level-by-level propagation using Breadth-First Search. Construct the same adjacency list of manager → subordinates, then push the head into a queue with time 0. Each time you process an employee, enqueue all direct subordinates with accumulated time currentTime + informTime[current].

Track the maximum time encountered during traversal. BFS simulates how information spreads outward through the company hierarchy. Each employee is visited once, and queue operations are constant time, resulting in O(n) time complexity and O(n) space for the queue and adjacency list.

BFS is particularly intuitive when you think of the message spreading simultaneously across different branches of the organization. The queue explicitly tracks the propagation frontier.

Recommended for interviews: The DFS solution is typically expected. It directly models the problem as finding the longest path from the head in a tree and produces a clean recursive implementation using Depth-First Search. BFS is equally efficient and shows that you understand message propagation simulations. Demonstrating both approaches signals strong command of tree traversal patterns.