Problem Description

Given an organizational hierarchy where each employee has a unique id and a manager id (or None if they are the CEO), you are to write a function that, given the entire list of employees and a specific manager id, returns a list of all employees (by their id) who report directly or indirectly to that manager. This includes employees managed by sub-managers down the tree. The input is typically a list of employee records, each with an id and manager id.

• Each employee has one direct manager (except the CEO, who has none).
• There are no cycles in the reporting structure.
• The output should not include the manager themselves, only their subordinates.
• All ids are unique.
• There is only one valid list of subordinates for a given manager.

Thought Process

At first glance, this problem resembles traversing a tree structure: each employee is a node, and the manager id forms parent-child links. The brute-force approach would be to, for each employee, check if their management chain leads to the given manager, but this would be slow and repetitive. Instead, we can optimize by first constructing the management tree, mapping each manager to their direct reports. Then, starting from the target manager, we traverse down the tree (using BFS or DFS) to collect all subordinates. This approach avoids redundant checks and leverages the hierarchical structure efficiently.

Solution Approach

Let's break down the algorithm step by step:

1. Build a Manager-to-Employees Map:
   • Iterate through the list of employees.
   • For each employee, add their id to a list mapped by their manager id.
   • This creates a dictionary (hash map) where each key is a manager, and the value is a list of their direct reports.
2. Traverse the Hierarchy:
   • Start from the given manager id.
   • Use either Depth-First Search (DFS) or Breadth-First Search (BFS) to visit all employees who report to this manager, directly or indirectly.
   • For each visited employee, add their id to the result list.
   • Continue recursively (or iteratively) for each subordinate.
3. Return the Result:
   • After traversing, return the list of collected employee ids.
   • Do not include the manager's own id in the result.

We use a hash map for fast lookups of subordinates, and DFS/BFS to ensure we capture all levels of the hierarchy.

Example Walkthrough

Sample Input:

    employees = [
        {"id": 1, "manager_id": None},   # CEO
        {"id": 2, "manager_id": 1},
        {"id": 3, "manager_id": 1},
        {"id": 4, "manager_id": 2},
        {"id": 5, "manager_id": 2},
        {"id": 6, "manager_id": 3}
    ]
    manager_id = 2
  

Step-by-step:

1. Build the manager-to-employees map:
   • 1: [2, 3]
   • 2: [4, 5]
   • 3: [6]
2. Start traversal from manager 2:
   • Direct reports: 4, 5
   • Neither 4 nor 5 have subordinates (not keys in the map)
3. Result: [4, 5]

If manager_id = 1 (the CEO), traversal would find [2, 3, 4, 5, 6], since all employees ultimately report to the CEO.

Time and Space Complexity

Brute-force Approach:

• For each employee, trace their management chain up to the root, checking if the chain contains the target manager.
• Worst-case time: O(N^2), where N is the number of employees.
• Space: O(1) extra, or O(N) if storing intermediate results.

• Building the manager-to-employees map: O(N)
• Traversing the subordinates: O(N) in the worst case (if all employees report up to the manager)
• Space: O(N) for the map and the result list

The optimized approach is O(N) time and space, which is efficient and scalable.

Summary

This problem is a classic application of tree traversal in a non-binary, real-world hierarchy. By mapping each manager to their direct reports, we efficiently traverse the reporting structure using DFS or BFS, collecting all subordinates. The key insight is to avoid redundant checks by leveraging the tree structure and using a hash map for fast lookups. This makes the solution both elegant and performant.

Code Implementation

def get_subordinates(employees, manager_id):
    from collections import defaultdict, deque

    # Build manager-to-employees map
    tree = defaultdict(list)
    for emp in employees:
        tree[emp['manager_id']].append(emp['id'])

    # Traverse using BFS
    result = []
    queue = deque(tree.get(manager_id, []))
    while queue:
        emp_id = queue.popleft()
        result.append(emp_id)
        queue.extend(tree.get(emp_id, []))
    return result
      

#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

struct Employee {
    int id;
    int manager_id; // Use -1 for None/CEO
};

vector<int> getSubordinates(const vector<Employee>& employees, int manager_id) {
    unordered_map<int, vector<int>> tree;
    for (const auto& emp : employees) {
        tree[emp.manager_id].push_back(emp.id);
    }
    vector<int> result;
    queue<int> q;
    if (tree.count(manager_id)) {
        for (int sub : tree[manager_id]) q.push(sub);
    }
    while (!q.empty()) {
        int eid = q.front(); q.pop();
        result.push_back(eid);
        if (tree.count(eid)) {
            for (int sub : tree[eid]) q.push(sub);
        }
    }
    return result;
}
      

import java.util.*;

class Employee {
    public int id;
    public Integer manager_id; // null for CEO
    public Employee(int id, Integer manager_id) {
        this.id = id;
        this.manager_id = manager_id;
    }
}

public class Solution {
    public List<Integer> getSubordinates(List<Employee> employees, int manager_id) {
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for (Employee emp : employees) {
            tree.computeIfAbsent(emp.manager_id, k -> new ArrayList<>()).add(emp.id);
        }
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        List<Integer> directSubs = tree.get(manager_id);
        if (directSubs != null) queue.addAll(directSubs);
        while (!queue.isEmpty()) {
            int eid = queue.poll();
            result.add(eid);
            List<Integer> subs = tree.get(eid);
            if (subs != null) queue.addAll(subs);
        }
        return result;
    }
}
      

function getSubordinates(employees, manager_id) {
    const tree = {};
    for (const emp of employees) {
        if (!(emp.manager_id in tree)) tree[emp.manager_id] = [];
        tree[emp.manager_id].push(emp.id);
    }
    const result = [];
    const queue = (tree[manager_id] || []).slice();
    while (queue.length) {
        const eid = queue.shift();
        result.push(eid);
        if (tree[eid]) queue.push(...tree[eid]);
    }
    return result;
}