Org Chart Depth and Business Head of Every Employee

Hard
241.

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. 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

ColumnType
emp_idint
full_namevarchar
designationvarchar
manager_idint

Primary key: emp_id.

manager_id is the emp_id of the employee's manager, NULL only for the CEO. Reporting lines never loop.

Example

The rows must come back in the order shown.

Employee

emp_idfull_namedesignationmanager_id
1Meera IyerCEONULL
2Arjun RaoCTO1
3Pooja ShahCFO1
4Karan NairEngineering Manager2
5Sneha DasSenior Engineer4
6Rahul KhanFinance Controller3
7Tanvi BoseEngineer5
8Dev MenonPlatform Lead2

Output

emp_idfull_namedepthbusiness_head
1Meera Iyer0NULL
2Arjun Rao1Arjun Rao
3Pooja Shah1Pooja Shah
4Karan Nair2Arjun Rao
6Rahul Khan2Pooja Shah
8Dev Menon2Arjun Rao
5Sneha Das3Arjun Rao
7Tanvi Bose4Arjun Rao
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

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

ColumnType
emp_idint
full_namevarchar
designationvarchar
manager_idint

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_idfull_namedesignationmanager_id
1Meera IyerCEONULL
2Arjun RaoCTO1
3Pooja ShahCFO1
4Karan NairEngineering Manager2
5Sneha DasSenior Engineer4
6Rahul KhanFinance Controller3
7Tanvi BoseEngineer5
8Dev MenonPlatform Lead2

Output

emp_idfull_namedepthbusiness_head
1Meera Iyer0NULL
2Arjun Rao1Arjun Rao
3Pooja Shah1Pooja Shah
4Karan Nair2Arjun Rao
6Rahul Khan2Pooja Shah
8Dev Menon2Arjun Rao
5Sneha Das3Arjun Rao
7Tanvi Bose4Arjun 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_id

Another 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 →