Analyze Organization Hierarchy solution and explanation
2 more videos on this problem
Most People Fail This SQL Interview Question | LeetCode HARD 3482 - Recursive CTE Logic ExplainedEveryday Data Science · 28:24 · 18K views
"LeetCode 3482: Analyze Organization Hierarchy | Easy SQL GuideInsightVanta · 32:43 · 918 views
Analyze Organization Hierarchy – LeetCode 3482 Explained (PostgreSQL)Sumanshu Nankana · 1:01:47 · 147 views
The problem
Table: Employees
+----------------+---------+ | Column Name | Type | +----------------+---------+ | employee_id | int | | employee_name | varchar | | manager_id | int | | salary | int | | department | varchar | +----------------+----------+ employee_id is the unique key for this table. Each row contains information about an employee, including their ID, name, their manager's ID, salary, and department. manager_id is null for the top-level manager (CEO).
Write a solution to analyze the organizational hierarchy and answer the following:
- Hierarchy Levels: For each employee, determine their level in the organization (CEO is level
1, employees reporting directly to the CEO are level2, and so on). - Team Size: For each employee who is a manager, count the total number of employees under them (direct and indirect reports).
- Salary Budget: For each manager, calculate the total salary budget they control (sum of salaries of all employees under them, including indirect reports, plus their own salary).
Return the result table ordered by the result ordered by level in ascending order, then by budget in descending order, and finally by employee_name in ascending order.
The result format is in the following example.
Example:
Input:
Employees table:
+-------------+---------------+------------+--------+-------------+ | 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 | +-------------+---------------+------------+--------+-------------+
Output:
+-------------+---------------+-------+-----------+--------+ | employee_id | employee_name | level | team_size | budget | +-------------+---------------+-------+-----------+--------+ | 1 | Alice | 1 | 9 | 84500 | | 3 | Charlie | 2 | 4 | 41500 | | 2 | Bob | 2 | 3 | 31000 | | 6 | Frank | 3 | 2 | 23000 | | 4 | David | 3 | 1 | 13500 | | 7 | Grace | 3 | 0 | 8500 | | 5 | Eva | 3 | 0 | 7500 | | 9 | Ivy | 4 | 0 | 7000 | | 10 | Judy | 4 | 0 | 7000 | | 8 | Hank | 4 | 0 | 6000 | +-------------+---------------+-------+-----------+--------+
Explanation:
- Organization Structure:
- Alice (ID: 1) is the CEO (level 1) with no manager
- Bob (ID: 2) and Charlie (ID: 3) report directly to Alice (level 2)
- David (ID: 4), Eva (ID: 5) report to Bob, while Frank (ID: 6) and Grace (ID: 7) report to Charlie (level 3)
- Hank (ID: 8) reports to David, and Ivy (ID: 9) and Judy (ID: 10) report to Frank (level 4)
- Level Calculation:
- The CEO (Alice) is at level 1
- Each subsequent level of management adds 1 to the level
- Team Size Calculation:
- Alice has 9 employees under her (the entire company except herself)
- Bob has 3 employees (David, Eva, and Hank)
- Charlie has 4 employees (Frank, Grace, Ivy, and Judy)
- David has 1 employee (Hank)
- Frank has 2 employees (Ivy and Judy)
- Eva, Grace, Hank, Ivy, and Judy have no direct reports (team_size = 0)
- Budget Calculation:
- Alice's budget: Her salary (12000) + all employees' salaries (72500) = 84500
- Charlie's budget: His salary (10000) + Frank's budget (23000) + Grace's salary (8500) = 41500
- Bob's budget: His salary (10000) + David's budget (13500) + Eva's salary (7500) = 31000
- Frank's budget: His salary (9000) + Ivy's salary (7000) + Judy's salary (7000) = 23000
- David's budget: His salary (7500) + Hank's salary (6000) = 13500
- Employees with no direct reports have budgets equal to their own salary
Note:
- The result is ordered first by level in ascending order
- Within the same level, employees are ordered by budget in descending order then by name in ascending order
Approach overview
Problem Overview: You get an employees table where each row points to its manager through manager_id. The task is to analyze the reporting tree, computing each employee's depth and the people reporting up through them, and return the result as a SQL query.
Approach 1: Iterative Self-Joins Per Level (O(n × d) time, O(n) space)
Start by joining the employees table to itself to find direct reports, then join again for the next level, and repeat until no rows come back. Each join adds one level of depth. The insight is that a hierarchy is just repeated manager-to-report edges, so you can expand one edge at a time. This works when you know the maximum depth in advance or when the org chart is shallow. It breaks down as depth grows because you write one join per level, and the query becomes unmaintainable. Use it only to build intuition about the tree structure.
Approach 2: Recursive CTE Traversal (O(n) time, O(n) space)
Define a WITH RECURSIVE common table expression. The anchor member selects the top of the hierarchy, where manager_id is null. The recursive member joins employees back to the CTE on manager_id = cte.employee_id and increments the level by one. The database expands the tree breadth-first until no new rows appear. Each employee is visited once, so total work is linear in the number of employees. This is the default approach on FleetCode for MySQL, and it scales to arbitrary depth without changing the query shape. Watch for cycles in bad data, since a loop in manager_id will recurse forever unless you cap depth or track visited nodes.
Approach 3: Pandas Adjacency Map with BFS (O(n) time, O(n) space)
In Pandas, build a dictionary mapping each manager to a list of direct reports, then run a breadth-first search from the roots using a queue. Track the level of each node as you enqueue it. Constructing the map is one pass over the dataframe, and the BFS visits each node once. This is the same logic as the recursive CTE, expressed in Python. Prefer it when the data already lives in a dataframe and you need the results in the same pipeline.
Recommended for interviews: Interviewers expect the recursive CTE. The self-join version shows you understand how the tree is built from edges, but the recursive CTE shows you can express traversal declaratively in SQL and handle arbitrary depth. Mention cycle protection and the O(n) bound to show you understand the tradeoffs.
Related topics: database, recursion, breadth-first search.
Solution
Thinking
Manager pointers form a tree; we need each person's level, team size, and team salary sum. The CEO has a null
manager_id.Levels expand top-down from the current manager set. Team size and budget must wait until children are done, so we fold in reverse id (or postorder).
Mark the CEO as level
1, recurse to tag direct reports aslevel+1, accumulateteam_sizeandbudget, and sort by level, budget descending, then name.
# Write your MySQL query statement below
WITH RECURSIVE
level_cte AS (
SELECT employee_id, manager_id, 1 AS level, salary FROM Employees
UNION ALL
SELECT a.employee_id, b.manager_id, level + 1, a.salary
FROM
level_cte a
JOIN Employees b ON b.employee_id = a.manager_id
),
employee_with_level AS (
SELECT a.employee_id, a.employee_name, a.salary, b.level
FROM
Employees a,
(SELECT employee_id, level FROM level_cte WHERE manager_id IS NULL) b
WHERE a.employee_id = b.employee_id
)
SELECT
a.employee_id,
a.employee_name,
a.level,
COALESCE(b.team_size, 0) AS team_size,
a.salary + COALESCE(b.budget, 0) AS budget
FROM
employee_with_level a
LEFT JOIN (
SELECT manager_id AS employee_id, COUNT(*) AS team_size, SUM(salary) AS budget
FROM level_cte
WHERE manager_id IS NOT NULL
GROUP BY manager_id
) b
ON a.employee_id = b.employee_id
ORDER BY level, budget DESC, employee_name;import pandas as pd
def analyze_organization_hierarchy(employees: pd.DataFrame) -> pd.DataFrame:
# Copy the input DataFrame to avoid modifying the original
employees = employees.copy()
employees['level'] = None
# Identify the CEO (level 1)
ceo_id = employees.loc[employees['manager_id'].isna(), 'employee_id'].values[0]
employees.loc[employees['employee_id'] == ceo_id, 'level'] = 1
# Recursively compute employee levels
def compute_levels(emp_df, level):
next_level_ids = emp_df[emp_df['level'] == level]['employee_id'].tolist()
if not next_level_ids:
return
emp_df.loc[emp_df['manager_id'].isin(next_level_ids), 'level'] = level + 1
compute_levels(emp_df, level + 1)
compute_levels(employees, 1)
# Initialize team size and budget dictionaries
team_size = {eid: 0 for eid in employees['employee_id']}
budget = {eid: salary for eid, salary in zip(employees['employee_id'], employees['salary'])}
# Compute team size and budget for each employee
for eid in employees.sort_values('level', ascending=False)['employee_id']:
manager_id = employees.loc[employees['employee_id'] == eid, 'manager_id'].values[0]
if pd.notna(manager_id):
team_size[manager_id] += team_size[eid] + 1
budget[manager_id] += budget[eid]
# Map computed team size and budget to employees DataFrame
employees['team_size'] = employees['employee_id'].map(team_size)
employees['budget'] = employees['employee_id'].map(budget)
# Sort the final result by level (ascending), budget (descending), and employee name (ascending)
employees = employees.sort_values(by=['level', 'budget', 'employee_name'], ascending=[True, False, True])
return employees[['employee_id', 'employee_name', 'level', 'team_size', 'budget']]Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Self-Joins | O(n × d) | O(n) | Shallow, fixed-depth hierarchies, learning the structure |
| Recursive CTE (default) | O(n) | O(n) | General case, any depth, MySQL |
| Pandas BFS | O(n) | O(n) | Data already in a dataframe, Python pipelines |
Frequently asked questions
Is Analyze Organization Hierarchy easy or hard?
It is rated hard, with a 62.9% acceptance rate. The difficulty comes from recognizing that the hierarchy requires recursion and from writing a correct recursive CTE with proper level tracking and termination.
How to solve Analyze Organization Hierarchy in O(n)?
Use a recursive CTE. The anchor selects employees with a null manager_id at level 0, and the recursive member joins employees to the CTE on manager_id equal to the previous employee_id while incrementing the level. Each employee gets processed once, which gives O(n) time and O(n) space.
Analyze Organization Hierarchy Python or Java solution?
For Python, the Pandas approach builds a manager-to-reports dictionary and runs BFS with a queue, which runs in O(n) time. Java and other languages are not the focus here because the problem is a database query, so the MySQL recursive CTE is the primary solution to learn.
What is the best approach for Analyze Organization Hierarchy?
The best approach is a recursive CTE in MySQL. It starts at the top of the hierarchy and walks down through manager_id links, visiting each employee once. This gives O(n) time and handles any depth without changing the query.
What data structure is used in Analyze Organization Hierarchy?
The input is a relational table that acts as an adjacency list, where each row stores a manager_id pointing to another employee_id. The solution uses a recursive common table expression for traversal. In Pandas, the same logic uses a dictionary mapping managers to reports and a queue for breadth-first search.
What is the time complexity of Analyze Organization Hierarchy?
The optimal solution runs in O(n) time, where n is the number of employees, because each employee is visited once during traversal. The iterative self-join approach is O(n × d), where d is the maximum depth, and it becomes slower as the hierarchy gets deeper.
Is Analyze Organization Hierarchy asked at Google, Amazon, or Meta?
The problem is tagged under Database on FleetCode, and it is a hard-rated SQL question. Company-specific frequency varies and is not confirmed by the tags alone, so check recent interview reports for your target company before relying on it.