Time Needed to Inform All Employees: Tree DFS Pattern

A company has n employees numbered from 0 to n - 1. The head of the company is the employee with id headID. Each employee has one direct manager given in the array manager, where manager[i] is the direct manager of employee i, and manager[headID] = -1. The head wants to inform all employees of urgent news. Each manager i needs informTime[i] minutes to inform all direct subordinates. Return the total number of minutes needed to inform all employees.

This is LeetCode 1376: Time Needed to Inform All Employees, and it is one of the best problems for learning how to compute maximum path sums in a tree using DFS.

Why this problem matters

Many tree problems ask you to compute something at each node and combine results from children. This problem is a clean example of that pattern: you build a tree from a flat array, then run DFS to find the longest path from root to any leaf. The "longest path" is not measured in edges but in accumulated inform times, which makes it a weighted path sum problem.

The same DFS pattern applies to problems like "Binary Tree Maximum Path Sum" (LeetCode 124), "Diameter of Binary Tree" (LeetCode 543), and "Maximum Depth of Binary Tree" (LeetCode 104). Once you are comfortable computing path sums with DFS here, those problems become variations of the same idea.

The key insight

The company hierarchy is a rooted tree. The head is the root, and each employee points to their manager (parent). To find the total time needed, you need the maximum sum of informTime values along any root-to-leaf path.

Why the maximum? Because the head informs all direct reports simultaneously. Each manager then informs their own subordinates simultaneously. The bottleneck is the longest chain of inform times, not the total of all inform times. This is the same reason that critical path analysis in project management focuses on the longest chain of dependent tasks.

The algorithm:

1. Build an adjacency list (children list) from the manager array so you can traverse from parent to children.
2. Run DFS from the head. At each node, recurse into all children.
3. For each node, the time to inform its entire subtree is informTime[node] + max(time for each child subtree).
4. The answer is the value returned by DFS at the root.

The solution

from collections import defaultdict

def num_of_minutes(n: int, head_id: int, manager: list[int], inform_time: list[int]) -> int:
    children = defaultdict(list)
    for i in range(n):
        if manager[i] != -1:
            children[manager[i]].append(i)

    def dfs(node: int) -> int:
        if not children[node]:
            return 0
        max_child_time = 0
        for child in children[node]:
            max_child_time = max(max_child_time, dfs(child))
        return inform_time[node] + max_child_time

    return dfs(head_id)

Let's walk through what each piece does.

The first loop builds an adjacency list from the manager array. For every employee (except the head), we add them as a child of their manager. This converts the flat parent-pointer representation into a tree we can traverse top-down.

The dfs function computes the maximum time needed to inform everyone in a subtree. If the current node is a leaf (no children), it takes 0 additional minutes because there is nobody left to inform. Otherwise, we recurse into every child, take the maximum time among all children, and add the current node's informTime. This captures the fact that the current manager informs all subordinates at once, so the bottleneck is the slowest child subtree.

The final call dfs(head_id) starts the traversal at the root of the company tree and returns the total time.

Visual walkthrough

Let's trace through the DFS step by step. Watch how the time accumulates along each root-to-leaf path, and how we take the maximum at each branching point.

Notice that every path from the head to a leaf gives a total time, and the answer is the maximum across all paths. In this example every path sums to 2, but in a less symmetric tree the paths would differ and the longest one would determine the answer.

Complexity analysis

Time is O(n) where n is the number of employees. Building the adjacency list takes O(n). The DFS visits each node exactly once, doing constant work per node (iterating over children, but each child is visited exactly once across the whole traversal). Total work is proportional to the number of employees.

Space is O(n). The adjacency list stores n - 1 edges. The DFS recursion stack can be O(n) deep in the worst case (a chain-shaped tree where every manager has exactly one subordinate). In a balanced tree the stack depth would be O(log n), but worst case is linear.

The building blocks

1. Building a tree from a parent array

The pattern of converting a flat manager (or parent) array into an adjacency list:

children = defaultdict(list)
for i in range(n):
    if manager[i] != -1:
        children[manager[i]].append(i)

Many tree problems give you the tree in a non-standard format: parent pointers, edge lists, or adjacency matrices. The first step is always converting to a structure you can traverse. This parent-to-children conversion is the most common one. You will reuse it in "Minimum Height Trees" (LeetCode 310), "Count Good Nodes" (LeetCode 1448), and any problem that gives you a parent array.

2. DFS for maximum weighted path

The pattern of computing the heaviest root-to-leaf path in a tree:

def dfs(node):
    if not children[node]:
        return 0
    return weight[node] + max(dfs(child) for child in children[node])

This is the weighted generalization of "maximum depth." You recurse into all children, take the maximum return value, and add the current node's weight. The base case is a leaf, which contributes 0. This pattern appears whenever you need the "critical path" through a tree, whether the weights represent time, cost, or distance.

3. Recognizing the tree structure

The problem description talks about managers and employees, not trees and nodes. Recognizing that the manager-subordinate relationship forms a rooted tree is the conceptual leap. Once you see it, the problem reduces to a standard tree traversal. Many medium and hard problems disguise trees as organizational charts, dependency chains, or hierarchical data. The skill is mapping the problem description to the underlying data structure.

Edge cases

Before submitting, think through these scenarios:

• Single employee: n = 1, the head is the only employee. No one needs to be informed. Return 0.
• Star-shaped tree: the head has n - 1 direct subordinates, all leaves. The answer is just informTime[headID] since all subordinates are informed simultaneously.
• Chain-shaped tree: every employee has exactly one subordinate. The answer is the sum of all informTime values, since there is only one root-to-leaf path.
• All inform times are 0 except the head: only the head has subordinates that need informing. The answer is informTime[headID].
• Large n with balanced tree: the DFS stack depth is O(log n), so no stack overflow risk. But a chain of 100,000 nodes could hit Python's recursion limit. In that case, convert to an iterative DFS or increase the recursion limit.

From understanding to recall

You have seen how to build a tree from a parent array and run DFS to find the maximum weighted path. The logic is clean: recurse into children, take the max, add the current weight. But writing it under interview pressure requires more than understanding.

The details that trip people up are small but costly. Do you use manager[i] as the key or the value when building the adjacency list? Do you add informTime before or after recursing? Do you return 0 for leaves or for nodes with no children? These are not conceptual mistakes. They are recall mistakes, and they slow you down when the clock is ticking.

Spaced repetition is how you eliminate them. You practice building the children map, writing the DFS function, and handling the base case from memory at increasing intervals. After a few rounds, you see "manager array" in a problem and the adjacency list construction flows out automatically. You see "maximum time to reach all leaves" and the DFS template is already in your fingers.

Related posts

• Maximum Depth of Binary Tree - The unweighted version of the same DFS pattern, where you add 1 per level instead of a variable weight
• Binary Tree Maximum Path Sum - A harder variant where the path can start and end at any node, not just root-to-leaf
• Course Schedule - Another problem that builds a graph from a dependency array and traverses it, using topological sort instead of DFS path sums

CodeBricks breaks Time Needed to Inform All Employees into its tree-building and DFS path-sum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a tree traversal problem shows up in your interview, you do not think about it. You just write it.