How I Solved the Employee Hierarchy Problem (LC 3482 for our reference), With a Recursive CTE
Hierarchical SQL problems can feel completely different from ordinary aggregation problems.
When I first attempted LeetCode 3482, I tried to solve it using the SQL concepts I already knew: joins, subqueries, grouping, and window functions. However, the organization can have an unknown number of levels. An employee may manage someone who manages another employee, who may manage another employee, and so on.
A fixed number of joins can only handle a fixed number of levels. What I needed was a query that could continue moving through the organization until no additional employees were found.
That is exactly what a recursive Common Table Expression, or recursive CTE, is designed to do.
In this article, I will explain:
- How to recognize a hierarchy problem
- How a recursive CTE works
- Why I included every employee in their own hierarchy
- How the query calculates team size and budget
- Why the hierarchy level must be taken from the CEO's perspective
- Why a recursive
JOINis more suitable than a correlated subquery here - How the complete solution fits together
My submitted solution performed better than 99% of accepted MySQL submissions at the time of submission. Runtime percentiles can change, but more importantly, this problem helped me understand how recursive SQL works.
The problem in simple terms
We are given an Employees table containing each employee's manager and salary.
+-------------+---------------+------------+--------+-------------+
| employee_id | employee_name | manager_id | salary | department |
+-------------+---------------+------------+--------+-------------+
| 1 | Alice | null | 12000 | Executive |
| 2 | Bob | 1 | 10000 | Sales |
| 3 | Charlie | 1 | 10000 | Engineering |
| 4 | David | 2 | 7500 | Sales |
| 5 | Eva | 2 | 7500 | Sales |
| 6 | Frank | 3 | 9000 | Engineering |
| 7 | Grace | 3 | 8500 | Engineering |
| 8 | Hank | 4 | 6000 | Sales |
| 9 | Ivy | 6 | 7000 | Engineering |
| 10 | Judy | 6 | 7000 | Engineering |
+-------------+---------------+------------+--------+-------------+
For every employee, we need to determine:
- Their level in the company hierarchy
- The number of employees in their complete team
- The total budget of that team
The complete team includes both direct and indirect reports. The budget includes the employee's own salary as well as the salaries of all direct and indirect reports.
Visualizing the organization
Before writing SQL, it helps to convert the table into a tree:
Alice (1)
├── Bob (2)
│ ├── David (4)
│ │ └── Hank (8)
│ └── Eva (5)
└── Charlie (3)
├── Frank (6)
│ ├── Ivy (9)
│ └── Judy (10)
└── Grace (7)
From this tree:
- Alice is at level 1.
- Bob and Charlie are at level 2.
- David, Eva, Frank, and Grace are at level 3.
- Hank, Ivy, and Judy are at level 4.
Alice's complete team contains every employee below her. Bob's complete team contains David, Eva, and Hank. Charlie's complete team contains Frank, Grace, Ivy, and Judy.
This is important because an ordinary self-join finds only one generation at a time. For example, joining Employees to itself once can find Bob's direct reports, David and Eva, but it does not automatically continue from David to Hank.
Why ordinary joins are not enough
A self-join can find direct reports:
SELECT
manager.employee_id,
report.employee_id AS report_id
FROM Employees AS manager
JOIN Employees AS report
ON report.manager_id = manager.employee_id;
We could add another join to find reports two levels below:
JOIN Employees AS second_level
ON second_level.manager_id = report.employee_id
But then we would need another join for the third level, another for the fourth level, and so on.
That approach assumes we already know the maximum depth of the organization. A recursive CTE does not require us to know that depth. It repeatedly applies the same relationship until no more matching employees exist.
How a recursive CTE works
A recursive CTE has two main parts:
WITH RECURSIVE cte_name AS (
-- Anchor query
UNION
-- Recursive query
)
The anchor query
The anchor query creates the initial rows. It answers the question:
Where should the recursion begin?
The recursive query
The recursive query uses rows already produced by the CTE to find the next set of rows. It answers the question:
Given the employees found in the previous step, who should be visited next?
The database keeps executing the recursive part for newly generated rows. The recursion stops naturally when an iteration produces no more rows.
The key idea in my solution
Instead of creating only one hierarchy starting from the CEO, I create a separate hierarchy starting from every employee.
This means:
- One hierarchy starts from Alice.
- Another starts from Bob.
- Another starts from Charlie.
- The same process is repeated for every employee.
Why do this?
Because the problem asks for the complete team and budget of every employee. If I built only the CEO's hierarchy, I would know where everyone is globally, but I would still need a way to identify every employee's descendants.
By building a hierarchy for every employee, all descendants of a particular employee share the same starting employee_id. I can then group by that starting ID to calculate the complete team size and budget.
Step 1: Start one hierarchy from every employee
The anchor query is:
SELECT
employee_id,
employee_id AS reporter_id,
1 AS level,
salary
FROM Employees
The full recursive CTE begins like this:
WITH RECURSIVE t AS (
SELECT
employee_id,
employee_id AS reporter_id,
1 AS level,
salary
FROM Employees
UNION
SELECT
t.employee_id,
e.employee_id,
t.level + 1,
e.salary
FROM t
JOIN Employees AS e
ON e.manager_id = t.reporter_id
)
The column names can be understood as follows:
-
employee_id: the employee whose complete hierarchy we are currently building -
reporter_id: the current person reached inside that hierarchy -
level: the current person's distance from the starting employee, with the starting employee at level 1 -
salary: the salary of the currentreporter_id
The distinction between employee_id and reporter_id is the most important part of the solution.
employee_id remains fixed throughout one hierarchy. reporter_id changes as the recursion moves downward.
For Bob's hierarchy, the rows conceptually look like this:
employee_id | reporter_id | level | salary
------------+-------------+-------+-------
2 | 2 | 1 | 10000
2 | 4 | 2 | 7500
2 | 5 | 2 | 7500
2 | 8 | 3 | 6000
The value 2 remains fixed in employee_id because all four rows belong to Bob's hierarchy. The reporter_id changes as Bob, David, Eva, and Hank are visited.
Step 2: Understand the recursive join
The recursive part is:
SELECT
t.employee_id,
e.employee_id,
t.level + 1,
e.salary
FROM t
JOIN Employees AS e
ON e.manager_id = t.reporter_id
For each current row in t, the query searches Employees for people whose manager_id equals the current reporter_id.
Suppose the current row in Bob's hierarchy is:
employee_id = 2
reporter_id = 2
level = 1
The join checks:
e.manager_id = 2
It finds David and Eva. The recursive query then produces:
2 | 4 | 2 | 7500
2 | 5 | 2 | 7500
The key detail is that recursion does not continue for only one returned row. If an iteration returns multiple rows, every newly returned row participates in the next recursive iteration.
Therefore:
- David is checked for reports.
- Eva is also checked for reports.
David manages Hank, so David's row produces:
2 | 8 | 3 | 6000
Eva manages nobody, so her branch produces no additional row and ends. The recursion continues independently for every active branch until no branch can produce another employee.
This was one of the most important things I learned from the problem: a recursive CTE expands every row returned by the previous iteration, not just one row.
Step 3: Why each employee includes themselves
In the anchor query, I set both IDs to the same value:
employee_id,
employee_id AS reporter_id
This includes every employee in their own hierarchy.
At first, that can look unnecessary because an employee is not their own report. However, it makes the budget calculation much cleaner.
For Bob, the required budget is:
Bob = 10000
David = 7500
Eva = 7500
Hank = 6000
----------------
Budget = 31000
Because Bob is already included in his own hierarchy, the budget can be calculated with one expression:
SUM(t1.salary)
We do not need to calculate the reports' salaries separately and then add Bob's salary afterward.
The team size should not include Bob himself. Since his hierarchy contains four rows but only three reports, it can be calculated as:
COUNT(*) - 1
This is a useful SQL design pattern: sometimes deliberately including a row simplifies one calculation, and a small adjustment makes the other calculation correct.
Step 4: Aggregate each employee's hierarchy
After the recursive CTE generates all hierarchies, the following query calculates each employee's team size and budget:
SELECT
t1.employee_id,
e.employee_name,
COUNT(*) - 1 AS team_size,
SUM(t1.salary) AS budget
FROM t AS t1
JOIN Employees AS e
ON t1.employee_id = e.employee_id
GROUP BY
t1.employee_id,
e.employee_name
For every starting employee_id:
-
COUNT(*) - 1counts all direct and indirect reports. -
SUM(t1.salary)adds the starting employee's salary and all descendant salaries. - The join retrieves the starting employee's name.
For Bob, this produces:
employee_id | employee_name | team_size | budget
------------+---------------+-----------+-------
2 | Bob | 3 | 31000
For Charlie, the hierarchy contains Charlie, Frank, Grace, Ivy, and Judy:
Charlie = 10000
Frank = 9000
Grace = 8500
Ivy = 7000
Judy = 7000
----------------
Budget = 41500
Charlie has four reports in total, so his aggregated values are:
employee_id | employee_name | team_size | budget
------------+---------------+-----------+-------
3 | Charlie | 4 | 41500
Step 5: The subtle problem with level
The recursive CTE creates a hierarchy starting from every employee. As a result, its level value is relative to the starting employee.
For example, these are valid rows in different hierarchies:
employee_id | reporter_id | level
------------+-------------+------
1 | 4 | 3
2 | 4 | 2
4 | 4 | 1
All three rows refer to David as reporter_id = 4, but they describe David from different starting points:
- David is level 3 from Alice's perspective.
- David is level 2 from Bob's perspective.
- David is level 1 from his own perspective.
The required result needs the global company level, not a relative level. Therefore, we need the hierarchy whose starting point is the CEO.
Step 6: Identify the CEO's hierarchy
The CEO is the employee whose manager_id is NULL:
SELECT employee_id
FROM Employees
WHERE manager_id IS NULL
Using the sample data, this returns Alice's ID, 1.
We then select only the recursive CTE rows whose starting employee_id is the CEO:
SELECT *
FROM t
WHERE employee_id = (
SELECT employee_id
FROM Employees
WHERE manager_id IS NULL
)
This produces Alice's complete hierarchy:
employee_id | reporter_id | level
------------+-------------+------
1 | 1 | 1
1 | 2 | 2
1 | 3 | 2
1 | 4 | 3
1 | 5 | 3
1 | 6 | 3
1 | 7 | 3
1 | 8 | 4
1 | 9 | 4
1 | 10 | 4
Because this hierarchy begins at the top of the organization, its levels are the global levels required by the problem.
In this result:
-
employee_idis always the CEO's ID. -
reporter_ididentifies the employee at that level.
That is why the final join matches the aggregated employee ID with level_table.reporter_id.
Step 7: Combine the calculations with the global levels
The aggregated subquery contains:
- Employee ID
- Employee name
- Team size
- Budget
The CEO-based hierarchy contains:
- Each employee's global level
The two results are joined as follows:
ON x.employee_id = level_table.reporter_id
This attaches the correct global level to every employee's aggregated result.
The final ordering is:
ORDER BY
level ASC,
budget DESC,
x.employee_name ASC
This means:
- Employees closer to the top appear first.
- Employees at the same level are ordered by larger budget first.
- Remaining ties are resolved alphabetically by employee name.
Complete MySQL solution
WITH RECURSIVE t AS (
SELECT
employee_id,
employee_id AS reporter_id,
1 AS level,
salary
FROM Employees
UNION
SELECT
t.employee_id,
e.employee_id,
t.level + 1,
e.salary
FROM t
JOIN Employees AS e
ON e.manager_id = t.reporter_id
)
SELECT
x.employee_id,
x.employee_name,
level_table.level,
x.team_size,
x.budget
FROM (
SELECT
t1.employee_id,
e.employee_name,
COUNT(*) - 1 AS team_size,
SUM(t1.salary) AS budget
FROM t AS t1
JOIN Employees AS e
ON t1.employee_id = e.employee_id
GROUP BY
t1.employee_id,
e.employee_name
) AS x
JOIN (
SELECT *
FROM t
WHERE employee_id = (
SELECT employee_id
FROM Employees
WHERE manager_id IS NULL
)
) AS level_table
ON x.employee_id = level_table.reporter_id
ORDER BY
level ASC,
budget DESC,
x.employee_name ASC;
Walking through the result
Using the sample hierarchy, the calculation for every employee is:
Alice -> reports: 9 -> budget: 84500 -> level: 1
Bob -> reports: 3 -> budget: 31000 -> level: 2
Charlie -> reports: 4 -> budget: 41500 -> level: 2
David -> reports: 1 -> budget: 13500 -> level: 3
Eva -> reports: 0 -> budget: 7500 -> level: 3
Frank -> reports: 2 -> budget: 23000 -> level: 3
Grace -> reports: 0 -> budget: 8500 -> level: 3
Hank -> reports: 0 -> budget: 6000 -> level: 4
Ivy -> reports: 0 -> budget: 7000 -> level: 4
Judy -> reports: 0 -> budget: 7000 -> level: 4
Alice's budget is the sum of all ten salaries:
12000 + 10000 + 10000 + 7500 + 7500
+ 9000 + 8500 + 6000 + 7000 + 7000
= 84500
After applying the requested ordering, Charlie appears before Bob at level 2 because Charlie has the larger budget. At level 3, Frank appears first, followed by David, Grace, and Eva according to descending budget.
Why I used a JOIN instead of a correlated subquery
While learning recursion, I wondered whether a correlated subquery could replace the recursive join.
The core operation is:
JOIN Employees AS e
ON e.manager_id = t.reporter_id
At every recursive step, we need to take the employees found in the previous step and produce a new set of employee rows. A join expresses exactly that relationship: match every current node with all of its children.
A scalar correlated subquery is usually expected to return one value. Even a set-returning correlated subquery does not, by itself, repeatedly feed its results back into the same operation for an unknown number of hierarchy levels.
The recursion provides the repetition, while the join provides the parent-to-child expansion. That is why recursive hierarchy queries commonly use a join in their recursive member.
UNION versus UNION ALL
My submitted solution uses UNION:
UNION
UNION removes duplicate rows, while UNION ALL retains them and usually avoids the work required for duplicate elimination.
In a valid employee tree where every employee has only one manager and there are no cycles, the recursive paths should not generate duplicate hierarchy rows. In that case, UNION ALL can also be appropriate:
UNION ALL
However, cycle handling deserves special attention in real-world systems. If invalid data allows employees to eventually report back to an employee already present in the same path, recursive traversal may repeat indefinitely or reach the database's recursion limit. Production queries may need explicit cycle detection, data constraints, or database-specific recursion safeguards.
For the LeetCode problem, the input represents a valid hierarchy, so the recursive structure is safe under the problem's assumptions.
Complexity discussion
Let n be the number of employees and let h be the total number of ancestor-descendant relationships generated across all employee hierarchies.
The CTE does not create only n rows. It creates one row for an employee and each employee in that person's subtree. Therefore, the generated row count depends on the shape of the organization.
- In a relatively balanced hierarchy, the number of generated relationships can be much smaller than the worst case.
- In a chain where every employee manages exactly one other employee, the CTE generates approximately
n + (n - 1) + ... + 1rows, which is quadratic. - The aggregation then processes those generated hierarchy rows.
A useful high-level description is therefore:
- Time: proportional to the hierarchy rows generated and processed, with a worst case of
O(n^2)for a chain-shaped organization - Space: proportional to the generated recursive result, also up to
O(n^2)in the worst case
The actual execution cost also depends on the database engine, indexes, recursive CTE implementation, and query plan. An index on manager_id is especially useful in a real database because the recursive join repeatedly searches for employees reporting to a particular manager.
Common mistakes in this type of problem
1. Counting only direct reports
Grouping employees by manager_id finds only direct reports. It misses employees farther down the hierarchy.
2. Using a fixed number of self-joins
This works only when the maximum hierarchy depth is known and small. It is not a general solution for an unknown-depth tree.
3. Losing the starting employee's identity
If the recursive CTE stores only the current employee being visited, it becomes difficult to know which root employee the row belongs to. Keeping a fixed starting employee_id solves this.
4. Using the relative level as the global level
Because every employee begins at level 1 in their own hierarchy, those levels cannot directly be used as company-wide levels. The global level must come from the CEO's hierarchy.
5. Forgetting whether budget includes the employee
The starting employee must be included in the salary sum. Including that employee in the anchor query makes the calculation straightforward.
6. Counting the employee as their own report
Because the employee is included for budget calculation, team size must subtract one.
7. Assuming recursion processes only one row at a time
If a recursive iteration finds several children, every child is used in the following iteration. Each branch continues independently until it reaches a leaf employee.
What this problem taught me
This problem was difficult for me because it required a different way of thinking about SQL.
Most SQL queries feel set-based and flat: filter rows, join tables, aggregate values, and return a result. A hierarchy is still processed using sets, but recursion allows the result of one iteration to become the input to the next iteration.
The most useful lessons I took from this problem were:
- Recognize unknown-depth relationships as a sign that recursion may be required.
- Separate the fixed root of a traversal from the current node being visited.
- Remember that every row produced by one recursive iteration can expand in the next.
- Design the CTE output around the final aggregation you need.
- Distinguish between a level relative to a selected employee and a level relative to the global root.
- Use joins in the recursive member to expand parent rows into child rows.
- Draw the hierarchy before writing the query.
A reusable recursive hierarchy pattern
The central idea can be generalized beyond this problem:
WITH RECURSIVE hierarchy AS (
SELECT
root_id,
current_id,
1 AS depth
FROM starting_rows
UNION ALL
SELECT
hierarchy.root_id,
child.id,
hierarchy.depth + 1
FROM hierarchy
JOIN source_table AS child
ON child.parent_id = hierarchy.current_id
)
SELECT *
FROM hierarchy;
This pattern appears in many real-world scenarios:
- Employee and manager structures
- Product categories and subcategories
- Folder and directory trees
- Bill-of-materials relationships
- Comment and reply threads
- Geographic region hierarchies
- Referral networks
The names of the tables and columns change, but the thought process remains similar:
- Choose the starting row or rows.
- Preserve the root identity.
- Track the current node.
- Join the current node to its children.
- Increase the depth.
- Stop when no children remain.
Final thoughts
Recursive CTEs looked intimidating when I first encountered them. The syntax was not the hardest part. The real challenge was understanding what each row represented and how the result of one iteration was used to generate the next.
For this solution, the breakthrough was to think in terms of two identities:
- The employee whose entire team I want to calculate
- The current employee being visited inside that team
Once those roles were separated into employee_id and reporter_id, the remaining steps became much clearer:
- Recursively build every employee's subtree.
- Include the employee themselves to simplify budget calculation.
- Group each subtree to calculate team size and budget.
- Use the CEO's subtree to obtain global hierarchy levels.
- Join the results and apply the required ordering.
This was not just another SQL problem for me. It introduced me to a way of solving hierarchies that ordinary joins and aggregations cannot handle cleanly on their own.
