Problem

Table: Employees

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| employee_id   | int     |
| employee_name | varchar |
| manager_id    | int     |
+---------------+---------+
employee_id is the column of unique values for this table.
Each row of this table indicates that the employee with ID employee_id and name employee_name reports his work to his/her direct manager with manager_id
The head of the company is the employee with employee_id = 1.

Write a solution to find employee_id of all employees that directly or indirectly report their work to the head of the company.

The indirect relation between managers will not exceed three managers as the company is small.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Input: 
Employees table:
+-------------+---------------+------------+
| employee_id | employee_name | manager_id |
+-------------+---------------+------------+
| 1           | Boss          | 1          |
| 3           | Alice         | 3          |
| 2           | Bob           | 1          |
| 4           | Daniel        | 2          |
| 7           | Luis          | 4          |
| 8           | Jhon          | 3          |
| 9           | Angela        | 8          |
| 77          | Robert        | 1          |
+-------------+---------------+------------+
Output: 
+-------------+
| employee_id |
+-------------+
| 2           |
| 77          |
| 4           |
| 7           |
+-------------+
Explanation: 
The head of the company is the employee with employee_id 1.
The employees with employee_id 2 and 77 report their work directly to the head of the company.
The employee with employee_id 4 reports their work indirectly to the head of the company 4 --> 2 --> 1. 
The employee with employee_id 7 reports their work indirectly to the head of the company 7 --> 4 --> 2 --> 1.
The employees with employee_id 3, 8, and 9 do not report their work to the head of the company directly or indirectly.

Solution

Method 1 - Using Recursive CTE

Intuition

The key idea is to use a recursive query to traverse the management hierarchy, starting from employees who directly report to the head (employee_id = 1), and then repeatedly finding employees who report to those employees, up to three levels deep. This way, we can collect all employees who directly or indirectly report to the head.

Approach

  1. Start by selecting employees whose manager_id is 1 (direct reports to the head).
  2. Use a recursive CTE to repeatedly find employees whose manager_id is in the set of employees already found (i.e., indirect reports).
  3. Limit the recursion to three levels, as the problem states the indirect relation will not exceed three managers.
  4. Exclude the head of the company from the result.
  5. Return the unique employee_id values found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

WITH RECURSIVE ReportChain AS (
  -- Step 1: Direct reports to the head
  SELECT employee_id, manager_id, 1 AS depth
  FROM Employees
  WHERE manager_id = 1 AND employee_id != 1

  UNION ALL

  -- Step 2: Indirect reports (up to 3 levels)
  SELECT e.employee_id, e.manager_id, rc.depth + 1
  FROM Employees e
  INNER JOIN ReportChain rc ON e.manager_id = rc.employee_id
  WHERE rc.depth < 3
)
SELECT DISTINCT employee_id
FROM ReportChain;

Complexity

  • ⏰ Time complexity: O(n), where n is the number of employees, since each employee is visited at most once per level (and levels are bounded).
  • 🧺 Space complexity: O(n), for storing the recursive CTE results.