Employee Importance: BFS Graph Traversal

You are given a list of employees, where each employee has an id, an importance value, and a list of direct subordinate ids. Given a single employee id, return the total importance value of that employee plus all of their subordinates, recursively. This is LeetCode 690: Employee Importance, and it is a clean exercise in building a hash map for fast lookups and then traversing an implicit graph with BFS.

The approach: hash map plus BFS

The employee data comes as a flat list, not a tree. If you want to find employee 2, you would have to scan the entire list each time. That is O(n) per lookup, which gets expensive fast. The fix is to build a hash map from employee id to the employee object before you start traversing. Once you have that map, every lookup is O(1).

With the map in hand, the traversal is a standard BFS. Start by placing the target employee's id in a queue. Pop an id from the queue, look up the employee in the map, add their importance to a running total, and push all of their subordinate ids onto the queue. Repeat until the queue is empty. Each employee is visited exactly once, so the total time is O(n).

You could also use DFS here. The logic is the same: look up the employee, add their importance, and recurse into each subordinate. BFS and DFS produce identical results for this problem because you are summing values across the entire subtree and the order does not matter.

def getImportance(employees: list['Employee'], id: int) -> int:
    lookup = {e.id: e for e in employees}
    total = 0
    queue = [id]
    while queue:
        eid = queue.pop(0)
        emp = lookup[eid]
        total += emp.importance
        queue.extend(emp.subordinates)
    return total

Step-by-step walkthrough

Complexity analysis

Both approaches visit every employee exactly once, so the time complexity is O(n) where n is the number of employees. The space complexity is also O(n): the hash map stores all n employees, and in the worst case the queue (BFS) or call stack (DFS) could hold all n employees too. For a balanced tree the queue or stack would be smaller, but the hash map still uses O(n) regardless.

The building blocks

Hash map for O(1) entity lookup

The employee list is flat. Without preprocessing, finding any employee by id requires a linear scan. Building a dictionary {e.id: e for e in employees} takes one pass over the list and gives you constant-time access to any employee by id after that. This is the same "build a lookup table first" pattern you see in problems like Two Sum, Clone Graph, and Course Schedule.

BFS over an implicit graph

The employee hierarchy is a tree, but it is not given to you as a tree data structure. It is a flat list where each entry says "my subordinates are ids [2, 3]." The hash map turns this flat list into something you can traverse like a graph. Pop an id, look it up, get the subordinate ids, push them onto the queue. The combination of a hash map and BFS lets you walk any implicit graph structure where edges are stored as references by id rather than direct pointers.

Edge cases

• Single employee, no subordinates. The target employee has no subordinates. The answer is just their own importance value. The queue starts with one id, processes it, finds no subordinates, and returns.
• Deeply nested hierarchy. If the tree is very deep (like a long chain of single subordinates), BFS handles it fine because the queue stays small. DFS would build up a deep call stack, which could be a concern in languages with limited recursion depth.
• Target employee is a leaf. Similar to the single-employee case. The leaf has no subordinates, so you sum just their importance and return immediately.
• Large importance values. The importance values can be negative (the problem allows it). Your summing logic does not need to change, but be aware that the total could be smaller than any individual importance value.
• All employees under one root. If every employee is a subordinate of the target (directly or indirectly), you end up summing every importance value in the list. The BFS visits all n employees, which is the worst case for queue size.

From understanding to recall

Solving this problem once teaches you the pattern, but retaining it requires repetition. The core idea (build a map, then BFS) is simple enough to remember, yet the details around queue management, subordinate expansion, and running totals can blur together with similar problems over time. Spaced repetition helps you lock in those details so that when you see a similar hierarchy traversal problem, the solution comes to you automatically instead of requiring a fresh derivation.

Related posts

• Clone Graph - BFS graph traversal with a hash map to track visited nodes, the same build-map-then-traverse pattern
• Number of Islands - BFS over a grid structure, another example of exploring all connected components
• Course Schedule - Graph traversal over entities with dependencies, similar to the subordinate hierarchy here