Org Chart Depth and Business Head of Every Employee
The company has exactly one CEO (manager_id NULL); everyone else reports to a manager who is also an employee.
- Difficulty: Hard
- Topics: Joins, Subqueries
- Dialect: MySQL
- Problem: #241
Problem statement
The company has exactly one CEO (manager_id NULL); everyone else reports to a manager who is also an employee. The people directly under the CEO are the business heads, and every other employee belongs to the business head at the top of their reporting chain.
Return every employee with emp_id, full_name, depth (0 for the CEO, 1 for a business head, 2 for their direct reports, and so on) and business_head (the business head's full_name; a business head is their own, and the CEO's is NULL). Order by depth, then emp_id.
Tables
Table: Employee
| Column | Type |
|---|---|
| emp_id | int |
| full_name | varchar |
| designation | varchar |
| manager_id | int |
Primary key: emp_id.
manager_id is the emp_id of the employee's manager, NULL only for the CEO. Reporting lines never loop.
Examples
Example 1
Employee
| emp_id | full_name | designation | manager_id |
|---|---|---|---|
| 1 | Meera Iyer | CEO | NULL |
| 2 | Arjun Rao | CTO | 1 |
| 3 | Pooja Shah | CFO | 1 |
| 4 | Karan Nair | Engineering Manager | 2 |
| 5 | Sneha Das | Senior Engineer | 4 |
| 6 | Rahul Khan | Finance Controller | 3 |
| 7 | Tanvi Bose | Engineer | 5 |
| 8 | Dev Menon | Platform Lead | 2 |
Output
| emp_id | full_name | depth | business_head |
|---|---|---|---|
| 1 | Meera Iyer | 0 | NULL |
| 2 | Arjun Rao | 1 | Arjun Rao |
| 3 | Pooja Shah | 1 | Pooja Shah |
| 4 | Karan Nair | 2 | Arjun Rao |
| 6 | Rahul Khan | 2 | Pooja Shah |
| 8 | Dev Menon | 2 | Arjun Rao |
| 5 | Sneha Das | 3 | Arjun Rao |
| 7 | Tanvi Bose | 4 | Arjun Rao |
How to solve Org Chart Depth and Business Head of Every Employee
Reporting chains have no fixed length, so this is a job for a recursive CTE. The anchor selects the business heads — employees whose manager is the CEO, i.e. whose manager's manager_id is NULL — with depth 1 and their own name as business_head. The recursive member joins Employee to the rows found so far on e.manager_id = c.emp_id: each pass reaches one level further down, adds 1 to the depth and copies the business head's name unchanged. The recursion stops when a pass finds no new reports; since reporting lines never loop, that always happens.
Anchoring at depth 1 rather than at the CEO is deliberate: the CEO has no business head, and starting the recursion with a NULL in that column would give the CTE an awkward column type in MySQL. Instead the final query LEFT JOINs Employee to the chain, so the one employee the recursion never reaches — the CEO — comes through with COALESCE(depth, 0) and a NULL head.
The alternative walks upwards: from every employee, follow manager_id one step at a time and record how many steps were taken. The longest walk is the depth, and the ancestor reached one step before the top is the business head. It visits each employee's whole chain, so it is O(n × depth), the same order as the top-down version.
Reference solution (MySQL)
WITH RECURSIVE chain AS (
SELECT e.emp_id, 1 AS depth, e.full_name AS business_head
FROM Employee e
JOIN Employee ceo ON ceo.emp_id = e.manager_id
WHERE ceo.manager_id IS NULL
UNION ALL
SELECT e.emp_id, c.depth + 1, c.business_head
FROM Employee e
JOIN chain c ON e.manager_id = c.emp_id
)
SELECT e.emp_id, e.full_name, COALESCE(c.depth, 0) AS depth, c.business_head
FROM Employee e
LEFT JOIN chain c ON c.emp_id = e.emp_id
ORDER BY depth, e.emp_idAnother way
WITH RECURSIVE up AS (
SELECT emp_id AS start_id, emp_id AS cur_id, manager_id AS cur_mgr, 0 AS steps FROM Employee
UNION ALL
SELECT u.start_id, m.emp_id, m.manager_id, u.steps + 1
FROM up u JOIN Employee m ON m.emp_id = u.cur_mgr
), depths AS (
SELECT start_id, MAX(steps) AS depth FROM up GROUP BY start_id
)
SELECT e.emp_id, e.full_name, d.depth, h.full_name AS business_head
FROM Employee e
JOIN depths d ON d.start_id = e.emp_id
LEFT JOIN up u ON u.start_id = e.emp_id AND u.steps = d.depth - 1
LEFT JOIN Employee h ON h.emp_id = u.cur_id
ORDER BY d.depth, e.emp_id← Staffing Pool of Multi-Skill Experts · Total Team Size and Payroll Under Each Manager →