CEO Subordinate Hierarchy

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     |
| salary        | int     |
+---------------+---------+
employee_id is the unique identifier for this table.
manager_id is the employee_id of the employee's manager. The CEO has a NULL manager_id.

Write a solution to find subordinates of the CEO (both direct and indirect), along with their level in the hierarchy and their salary difference from the CEO.

The result should have the following columns:

The query result format is in the following example.

subordinate_id: The employee_id of the subordinate
subordinate_name: The name of the subordinate
hierarchy_level: The level of the subordinate in the hierarchy (1 for direct reports, 2 for their direct reports, and so on)
salary_difference: The difference between the subordinate’s salary and the CEO’s salary

Return the result table ordered by hierarchy_level ascending , and then by subordinate_id ascending.

The query result format is in the following example.

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
30
31
32
33
34


Input:
`Employees` table:
+-------------+----------------+------------+---------+
| employee_id | employee_name  | manager_id | salary  |
+-------------+----------------+------------+---------+
| 1           | Alice          | NULL       | 150000  |
| 2           | Bob            | 1          | 120000  |
| 3           | Charlie        | 1          | 110000  |
| 4           | David          | 2          | 105000  |
| 5           | Eve            | 2          | 100000  |
| 6           | Frank          | 3          | 95000   |
| 7           | Grace          | 3          | 98000   |
| 8           | Helen          | 5          | 90000   |
+-------------+----------------+------------+---------+
Output:
+----------------+------------------+------------------+-------------------+
| subordinate_id | subordinate_name | hierarchy_level  | salary_difference |
+----------------+------------------+------------------+-------------------+
| 2              | Bob              | 1                | -30000            |
| 3              | Charlie          | 1                | -40000            |
| 4              | David            | 2                | -45000            |
| 5              | Eve              | 2                | -50000            |
| 6              | Frank            | 2                | -55000            |
| 7              | Grace            | 2                | -52000            |
| 8              | Helen            | 3                | -60000            |
+----------------+------------------+------------------+-------------------+
Explanation:
* Bob and Charlie are direct subordinates of Alice (CEO) and thus have a hierarchy_level of 1.
* David and Eve report to Bob, while Frank and Grace report to Charlie, making them second-level subordinates (hierarchy_level 2).
* Helen reports to Eve, making Helen a third-level subordinate (hierarchy_level 3).
* Salary differences are calculated relative to Alice's salary of 150000.
* The result is ordered by hierarchy_level ascending, and then by subordinate_id ascending.
**Note:** The output is ordered first by hierarchy_level in ascending order,
then by subordinate_id in ascending order.

Solution

Method 1 – Recursive CTE for Hierarchy Traversal

Intuition: To find all subordinates (direct and indirect) of the CEO, we can use a recursive CTE to traverse the hierarchy tree. At each step, we track the current level and calculate the salary difference from the CEO. This approach efficiently finds all subordinates at all levels.

Approach:

Identify the CEO (the employee with manager_id IS NULL).
Use a recursive CTE:
- The base case selects all direct subordinates of the CEO (level 1).
- The recursive case joins subordinates to their managers, incrementing the level.
For each subordinate, calculate the salary difference from the CEO.
Select the required columns and order by hierarchy_level and subordinate_id.

Code

 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
30
31
32
33


WITH RECURSIVE Hierarchy AS (
  -- Base case: direct subordinates of CEO
  SELECT
    e.employee_id AS subordinate_id,
    e.employee_name AS subordinate_name,
    1 AS hierarchy_level,
    e.salary - ceo.salary AS salary_difference,
    e.employee_id,
    ceo.salary AS ceo_salary
  FROM Employees e
  JOIN Employees ceo ON ceo.manager_id IS NULL
  WHERE e.manager_id = ceo.employee_id

  UNION ALL

  -- Recursive case: subordinates of subordinates
  SELECT
    e.employee_id AS subordinate_id,
    e.employee_name AS subordinate_name,
    h.hierarchy_level + 1 AS hierarchy_level,
    e.salary - h.ceo_salary AS salary_difference,
    e.employee_id,
    h.ceo_salary
  FROM Employees e
  JOIN Hierarchy h ON e.manager_id = h.subordinate_id
)
SELECT
  subordinate_id,
  subordinate_name,
  hierarchy_level,
  salary_difference
FROM Hierarchy
ORDER BY hierarchy_level ASC, subordinate_id ASC;

Complexity

⏰ Time complexity: O(N), where N is the number of employees (each employee is visited once).
🧺 Space complexity: O(N) for the recursion stack and result set.

Problem#

Example 1:#

Solution#

Method 1 – Recursive CTE for Hierarchy Traversal#

Code#

Complexity#