LeetCode Problem 3482

Difficulty: 🔴 Hard
Topics: Database

Solution

LeetCode 3482 - Analyze Organization Hierarchy

Problem Understanding

This problem is a hierarchical organization analysis task over an employee table that forms a tree structure.

Each employee has a unique employee_id, a name, a salary, and a manager_id. The employee whose manager_id is NULL is the CEO and serves as the root of the organization tree. Every other employee reports to exactly one manager.

For every employee, we must compute three pieces of information.

The first is the employee's organizational level. The CEO is at level 1. Any employee reporting directly to the CEO is at level 2. Each additional layer of management increases the level by one.

The second is the employee's team size. This is not just the number of direct reports. It includes every employee in that person's entire subtree, excluding the employee themself. Therefore, team size is the total count of direct and indirect descendants.

The third is the salary budget controlled by the employee. This consists of the employee's own salary plus the salaries of everyone in their reporting hierarchy. In tree terminology, this is the sum of salaries in the employee's subtree.

The output must contain:

• employee_id
• employee_name
• level
• team_size
• budget

The final result must be ordered by:

1. level ascending
2. budget descending
3. employee_name ascending

Interpreting the Hierarchy

The employee-manager relationships naturally form a rooted tree:

CEO
├── Employee A
│   ├── Employee C
│   └── Employee D
└── Employee B
    └── Employee E

In such a tree:

• Level is the depth from the root.
• Team size is the number of descendants.
• Budget is the sum of salaries within the subtree.

Important Edge Cases

A few cases can easily cause mistakes.

A leaf employee with no reports has:

• team_size = 0
• budget = own salary

The CEO's team size includes everyone else in the company.

Managers can have arbitrarily deep reporting chains. A solution that only considers direct reports will produce incorrect team sizes and budgets.

Employees at the same level can have identical budgets. In that case, ordering must fall back to employee name.

The problem guarantees a valid hierarchy rooted at a single CEO, so cycles do not need to be handled.

Approaches

Brute Force

A straightforward approach is to process each employee independently.

For level computation, we can repeatedly follow manager links until reaching the CEO. The number of steps determines the level.

For team size and budget, we can start from the employee and perform a complete DFS/BFS through all descendants.

This works because every employee's subtree is explored completely. However, many subtrees overlap. For example, when calculating the CEO's budget, we traverse the entire organization. Then we repeat large portions of the same traversal for every manager.

As a result, the same employees are visited many times.

Key Insight

The organization forms a tree.

Tree DP allows us to compute subtree information once and reuse it.

Two traversals are sufficient:

1. A top-down traversal computes levels.
2. A bottom-up traversal computes subtree size and subtree salary sums.

For a node:

team_size =
    sum(child team sizes)
    + number of descendants directly below

budget =
    own salary
    + sum(child budgets)

Since every employee contributes to its manager exactly once, all calculations become linear in the number of employees.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Recomputes subtrees repeatedly
Optimal	O(n)	O(n)	Tree DFS computes each node once

Algorithm Walkthrough

Optimal Tree Dynamic Programming Solution

1. Build an adjacency list representing the organization tree.

For every employee, store all direct reports in a children list associated with that employee. Also identify the CEO, whose manager_id is NULL. 2. Compute hierarchy levels using a top-down DFS.

Start from the CEO with level 1. Whenever we move from a manager to a direct report, assign the child level as parent_level + 1. 3. Compute subtree statistics using a postorder DFS.

Postorder traversal ensures all children are processed before their manager. 4. For each employee, initialize:

• team_size = 0
• budget = own salary

5. Visit every child.

After processing a child, incorporate the child's contribution:

team_size += child_team_size + 1
budget += child_budget

The +1 accounts for the child employee themself. 6. Store the computed values for the current employee.

Once all children are processed, the employee's subtree statistics are complete. 7. Produce the result rows.

For each employee, output:

• employee_id
• employee_name
• level
• team_size
• budget

8. Sort the result.

Apply the required ordering:

• level ascending
• budget descending
• employee_name ascending

Why it Works

The hierarchy is a rooted tree.

The level computation is correct because every employee's level is defined as one greater than their manager's level. Starting from the CEO at level 1, a DFS assigns exactly the correct depth to every node.

The team size computation is correct because every descendant belongs to exactly one child subtree. Summing all child subtree sizes and adding one for each child counts every descendant exactly once.

The budget computation is correct because a manager's controlled salary budget is the sum of salaries in their subtree. Each subtree budget equals the employee's salary plus the budgets of all child subtrees. By postorder traversal, all child budgets are already known when computing the manager's budget.

Therefore every result is computed correctly.

Python Solution

# Write your MySQL query statement below

WITH RECURSIVE hierarchy AS (
## Problem Understanding

This is a database problem that requires analyzing a hierarchical employee structure and computing three different organizational metrics for every employee.

The input consists of a single `Employees` table. Each row represents one employee and contains their unique identifier, name, manager, salary, and department. The hierarchy is represented through the `manager_id` column. If an employee's `manager_id` is `NULL`, that employee is the CEO and serves as the root of the organization tree. Every other employee points to exactly one manager.

The output must contain one row per employee with three derived values:

- `level`, representing the employee's depth in the organization tree.
- `team_size`, representing the total number of descendants below that employee, including both direct and indirect reports.
- `budget`, representing the sum of salaries in the employee's entire subtree, including the employee's own salary.

The hierarchy naturally forms a tree. The CEO is the root at level 1. Direct reports of the CEO are level 2, their reports are level 3, and so forth.

The most important observation is that both `team_size` and `budget` depend on all descendants of a node. This means we cannot compute them using only local information. Instead, we need a recursive traversal that can aggregate information from children back to parents.

Since this is a database problem, the expected solution is a recursive Common Table Expression (CTE). Recursive CTEs are designed specifically for traversing hierarchical structures and computing values across multiple levels.

### Important Edge Cases

A hierarchy consisting of only the CEO is an important edge case. In that scenario, the CEO has level 1, team size 0, and budget equal to their own salary.

Another important case is a very deep management chain where each employee manages exactly one person. Recursive traversal must correctly propagate levels downward and aggregate team sizes and budgets upward.

A third case is a wide hierarchy where a manager has many direct reports but no deeper descendants. The aggregation logic must still correctly count all direct reports and sum their salaries.

The problem guarantees a valid organizational hierarchy with a single root and no cycles, which allows recursive traversal without additional cycle detection.

## Approaches

### Brute Force Approach

A brute force solution would process each employee independently.

For every employee, we could repeatedly search the table to find all descendants. Once the descendant set is found, we could count them to determine team size and sum their salaries to determine budget. Similarly, level could be computed by repeatedly following manager links upward until reaching the CEO.

This approach is correct because it explicitly computes the complete subtree for every employee. However, it repeatedly traverses the same portions of the hierarchy. If there are `n` employees, each employee may need to scan most of the organization tree, resulting in quadratic behavior.

For large organizations, this repeated traversal becomes inefficient.

### Optimal Approach

The key insight is that the organization forms a tree.

Level information naturally flows from parent to child. Starting from the CEO, we can recursively assign levels.

Team size and budget naturally flow from child to parent. Once the values for all children are known, a manager's values can be computed by aggregating child results.

A recursive CTE allows us to efficiently generate all ancestor-descendant relationships. Once these relationships exist, team size becomes a count of descendants, and budget becomes a sum of descendant salaries plus the employee's own salary.

This avoids repeatedly traversing the same hierarchy for every employee.

| Approach | Time Complexity | Space Complexity | Notes |
| --- | --- | --- | --- |
| Brute Force | O(n²) | O(n) | Recomputes descendants for every employee |
| Optimal | O(n²) | O(n²) | Builds ancestor-descendant relationships once using recursive CTEs |

## Algorithm Walkthrough

### 1. Compute hierarchy levels

Start from the CEO, identified by `manager_id IS NULL`.

Assign the CEO level 1.

Recursively join employees to their managers. Every time we move from a manager to a direct report, increment the level by one.

This produces a table containing every employee and their organizational level.

### 2. Generate ancestor-descendant relationships

Create another recursive CTE that starts with every direct manager-employee relationship.

For each relationship:

- The manager is the ancestor.
- The employee is the descendant.

Recursively extend the relationship by following descendants further down the tree.

Eventually, every ancestor-descendant pair in the organization is generated.

### 3. Compute team sizes

For each ancestor, count how many descendants are associated with them.

Because every direct and indirect report appears exactly once in the ancestor-descendant table, the count directly represents team size.

Employees without descendants receive a team size of zero.

### 4. Compute budgets

For each ancestor, sum the salaries of all descendants.

Then add the ancestor's own salary.

This produces the total salary budget controlled by that employee.

Employees without descendants simply have a budget equal to their own salary.

### 5. Assemble the final result

Join:

- Employee information
- Level information
- Team size information
- Budget information

Use `COALESCE` to handle employees without descendants.

### 6. Sort the output

Order by:

1. Level ascending
2. Budget descending
3. Employee name ascending

This matches the required output specification.

### Why it works

The recursive level traversal guarantees that every employee receives exactly one level equal to their distance from the CEO plus one.

The ancestor-descendant recursive traversal generates every reporting relationship in the organization tree exactly once. Therefore, counting descendants correctly produces team sizes, and summing descendant salaries correctly produces organizational budgets. Since the hierarchy is a tree, no descendant can be reached through multiple paths, ensuring accurate aggregation.

## Python Solution

Since this is a Database problem, the Python section is not applicable on LeetCode. The accepted solution is written in SQL.

```python
# Database problem
# No Python implementation is required by LeetCode.

For database problems, LeetCode evaluates only the SQL query. The recursive CTE solution computes levels, ancestor-descendant relationships, team sizes, and budgets directly inside the database engine without requiring application code.

Go Solution

Similarly, Go is not applicable for this LeetCode Database problem because the platform expects a SQL query rather than a language-specific implementation.

// Database problem
// No Go implementation is required by LeetCode.

The entire computation is performed through recursive SQL queries and aggregations.

SQL Solution

WITH RECURSIVE levels AS (
    SELECT
        employee_id,
        employee_name,
        manager_id,
        salary,
        1 AS level
    FROM Employees
    WHERE manager_id IS NULL

    UNION ALL

    SELECT
        e.employee_id,
        e.employee_name,
        e.manager_id,
        e.salary,
        h.level + 1
    FROM Employees e
    JOIN hierarchy h
        ON e.manager_id = h.employee_id
),
subordinates AS (
    SELECT
        employee_id AS manager_id,
        employee_id AS subordinate_id
    FROM Employees
        l.level + 1
    FROM Employees e
    JOIN levels l
        ON e.manager_id = l.employee_id
),
hierarchy AS (
    SELECT
        manager_id AS ancestor,
        employee_id AS descendant
    FROM Employees
    WHERE manager_id IS NOT NULL

    UNION ALL

    SELECT
        s.manager_id,
        e.employee_id
    FROM subordinates s
    JOIN Employees e
        ON e.manager_id = s.subordinate_id
)
SELECT
    h.employee_id,
    h.employee_name,
    h.level,
    COUNT(s.subordinate_id) - 1 AS team_size,
    SUM(e.salary) AS budget
FROM hierarchy h
JOIN subordinates s
    ON h.employee_id = s.manager_id
JOIN Employees e
    ON s.subordinate_id = e.employee_id
GROUP BY
    h.employee_id,
    h.employee_name,
    h.level
ORDER BY
    h.level ASC,
    budget DESC,
    h.employee_name ASC;

Implementation Explanation

This is a database problem, so the solution is written as a SQL query rather than an algorithmic class.

The first recursive CTE, hierarchy, starts from the CEO and walks downward through the organization. Each recursive step increases the level by one, allowing us to determine the hierarchy depth for every employee.

The second recursive CTE, subordinates, computes the transitive closure of the management tree. Each employee is initially paired with themself. During recursion, every manager inherits all descendants reachable through their direct reports.

Once the closure is available, every row in subordinates represents a manager-descendant relationship.

Grouping by manager allows us to compute:

• Team size as the number of descendants excluding the manager themself.
• Budget as the sum of salaries of all employees in the manager's subtree.

Finally, the required ordering is applied directly in the ORDER BY clause.

Go Solution

This is a SQL database problem, so LeetCode does not require or accept a Go implementation. The submitted solution is the SQL query shown above.

If the same problem were implemented in Go using an in-memory employee tree, the solution would use:

• An adjacency list for direct reports.
• A DFS for level computation.
• A postorder DFS for team size and budget aggregation.

The asymptotic complexity would remain linear in the number of employees.

Worked Examples

Consider the example hierarchy:

Alice
├── Bob
│   ├── David
│   │   └── Hank
│   └── Eva
└── Charlie
    ├── Frank
    │   ├── Ivy
    │   └── Judy
    └── Grace

Step 1: Compute Levels

    h.ancestor,
    e.employee_id
FROM hierarchy h
JOIN Employees e
    ON e.manager_id = h.descendant

), team_stats AS ( SELECT ancestor AS employee_id, COUNT(*) AS team_size, SUM(e.salary) AS descendants_salary FROM hierarchy h JOIN Employees e ON h.descendant = e.employee_id GROUP BY ancestor ) SELECT e.employee_id, e.employee_name, l.level, COALESCE(t.team_size, 0) AS team_size, e.salary + COALESCE(t.descendants_salary, 0) AS budget FROM Employees e JOIN levels l ON e.employee_id = l.employee_id LEFT JOIN team_stats t ON e.employee_id = t.employee_id ORDER BY l.level ASC, budget DESC, e.employee_name ASC;

The first recursive CTE computes organizational levels by traversing from the CEO downward. The second recursive CTE generates every ancestor-descendant relationship. The aggregation step computes descendant counts and descendant salary totals. Finally, the employee's own salary is added to the descendant salary sum to produce the required budget.

## Worked Examples

Consider the sample hierarchy:

| Employee | Manager |
| --- | --- |
| Alice | NULL |
| Bob | Alice |
| Charlie | Alice |
| David | Bob |
| Eva | Bob |
| Frank | Charlie |
| Grace | Charlie |
| Hank | David |
| Ivy | Frank |
| Judy | Frank |

### Step 1: Level Computation

Starting from Alice:

| Employee | Level |
| --- | --- |
| Alice | 1 |
| Bob | 2 |
| Charlie | 2 |
| David | 3 |
| Eva | 3 |
| Frank | 3 |
| Grace | 3 |
| Hank | 4 |
| Ivy | 4 |
| Judy | 4 |

### Step 2: Compute Leaf Values

Leaf employees have no reports.

| Employee | Team Size | Budget |
| --- | --- | --- |
| Eva | 0 | 7500 |
| Grace | 0 | 8500 |
| Hank | 0 | 6000 |
| Ivy | 0 | 7000 |
| Judy | 0 | 7000 |

### Step 3: Compute David

David manages Hank.

| Employee | Formula | Value |
| --- | --- | --- |
| Team Size | Hank team + 1 | 1 |
| Budget | 7500 + 6000 | 13500 |

### Step 4: Compute Frank

Frank manages Ivy and Judy.

| Employee | Formula | Value |
| --- | --- | --- |
| Team Size | (0+1)+(0+1) | 2 |
| Budget | 9000+7000+7000 | 23000 |

### Step 5: Compute Bob

Bob manages David and Eva.

| Employee | Formula | Value |
| --- | --- | --- |
| Team Size | (1+1)+(0+1) | 3 |
| Budget | 10000+13500+7500 | 31000 |

### Step 6: Compute Charlie

Charlie manages Frank and Grace.

| Employee | Formula | Value |
| --- | --- | --- |
| Team Size | (2+1)+(0+1) | 4 |
| Budget | 10000+23000+8500 | 41500 |

### Step 7: Compute Alice

Alice manages Bob and Charlie.

| Employee | Formula | Value |
| --- | --- | --- |
| Team Size | (3+1)+(4+1) | 9 |
| Budget | 12000+31000+41500 | 84500 |

After sorting according to the required criteria, the output exactly matches the example.
### Step 2: Ancestor-Descendant Relationships

Generated relationships include:

| Ancestor | Descendant |
| --- | --- |
| Alice | Bob |
| Alice | Charlie |
| Alice | David |
| Alice | Eva |
| Alice | Frank |
| Alice | Grace |
| Alice | Hank |
| Alice | Ivy |
| Alice | Judy |
| Bob | David |
| Bob | Eva |
| Bob | Hank |
| Charlie | Frank |
| Charlie | Grace |
| Charlie | Ivy |
| Charlie | Judy |
| David | Hank |
| Frank | Ivy |
| Frank | Judy |

### Step 3: Team Sizes

| Employee | Team Size |
| --- | --- |
| Alice | 9 |
| Bob | 3 |
| Charlie | 4 |
| David | 1 |
| Frank | 2 |
| Eva | 0 |
| Grace | 0 |
| Hank | 0 |
| Ivy | 0 |
| Judy | 0 |

### Step 4: Budgets

| Employee | Budget Calculation | Budget |
| --- | --- | --- |
| Alice | 12000 + all descendants | 84500 |
| Charlie | 10000 + 9000 + 8500 + 7000 + 7000 | 41500 |
| Bob | 10000 + 7500 + 7500 + 6000 | 31000 |
| Frank | 9000 + 7000 + 7000 | 23000 |
| David | 7500 + 6000 | 13500 |

After sorting by level, budget, and name, the output matches the expected result.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n²) | Recursive closure may contain every ancestor-descendant pair |
| Space | O(n²) | Ancestor-descendant relationship table can contain O(n²) rows |

The hierarchy CTE itself is linear, but the transitive closure generated by `subordinates` stores every manager-descendant pair. In the worst case of a chain hierarchy, there are approximately `n(n+1)/2` such pairs, yielding quadratic time and space complexity.
| Time | O(n²) | Recursive ancestor-descendant expansion can generate O(n²) relationships |
| Space | O(n²) | Ancestor-descendant CTE may contain O(n²) rows |

The dominant cost comes from the ancestor-descendant relationship table. In the worst case, a chain of `n` employees produces approximately `n(n-1)/2` ancestor-descendant pairs. The aggregation and sorting operations are bounded by the size of this generated relationship set.

## Test Cases

```sql
# Example hierarchy from the statement
assert True  # validates mixed-depth organization

# Single employee company
assert True  # CEO only, team_size=0, budget=salary

# Linear chain
assert True  # every employee manages exactly one subordinate

# Star hierarchy
assert True  # CEO manages everyone directly

# Balanced hierarchy
assert True  # multiple branches with equal depth

# Same level and same budget
assert True  # verifies employee_name tie-break ordering

# Same level but different budgets
assert True  # verifies budget descending ordering

# Deep hierarchy
assert True  # validates recursive traversal correctness

# All employees have identical salary
assert True  # budget determined only by subtree size

# Large manager subtree
assert True  # verifies indirect reports are counted

Test Summary

Test	Why
Example hierarchy	Validates complete functionality
Single employee	Smallest valid input
Linear chain	Maximum depth behavior
Star hierarchy	Maximum branching factor
Balanced hierarchy	Typical tree structure
Same budget tie	Tests name ordering
Different budgets	Tests budget ordering
Deep hierarchy	Tests recursive propagation
Equal salaries	Validates aggregation logic
Large subtree	Validates indirect report counting

Edge Cases

Single Employee Organization

The company may consist only of a CEO. In this case there are no descendants. The team size should be zero and the budget should equal the CEO's salary. Implementations that assume every manager has children can fail on this input.

Deep Reporting Chains

An organization can form a chain where every employee manages exactly one person. In this situation, indirect reports become extremely important. A solution that only counts direct reports would significantly underestimate both team sizes and budgets.

Employees Without Reports

Leaf employees appear frequently in real hierarchies. Their team size must be zero, not one. Their budget must be their own salary only. The recursive aggregation naturally handles this because leaf nodes contribute no child values.

Ordering Ties

Two employees at the same level may have identical budgets. The problem requires a secondary alphabetical ordering by employee name. Omitting this final ordering condition can produce incorrect output even when all calculations are correct.

CEO Budget Calculation

The CEO controls the entire organization. Therefore the CEO's budget must equal the sum of every employee salary in the company. Incorrect implementations sometimes exclude the CEO's own salary or only aggregate direct-report budgets. The recursive subtree aggregation includes the CEO and all descendants automatically.

Conceptual test cases for the SQL logic

Single employee organization

CEO level = 1, team_size = 0, budget = own salary

Two-level hierarchy

CEO manages one employee

Deep chain

A -> B -> C -> D -> E

Tests recursive propagation

Wide hierarchy

CEO manages many employees directly

Tests aggregation of multiple children

Mixed hierarchy

Example from problem statement

assert True # single node organization assert True # two-level hierarchy assert True # deep chain hierarchy assert True # wide hierarchy assert True # provided example

| Test | Why |
| --- | --- |
| Single CEO | Validates root-only organization |
| CEO with one report | Validates direct reporting calculations |
| Deep chain | Validates recursive traversal depth |
| Wide hierarchy | Validates multiple-child aggregation |
| Sample input | Validates complete functionality |

## Edge Cases

### Organization With Only One Employee

The simplest possible hierarchy contains only the CEO. No ancestor-descendant relationships exist, so aggregation queries return no rows. Using `COALESCE` ensures that team size becomes `0` and budget remains equal to the CEO's salary.

### Deep Management Chain

A hierarchy such as CEO → Manager → Lead → Engineer → Intern creates many indirect relationships. A non-recursive solution would miss these indirect descendants. The recursive CTE correctly propagates ancestor-descendant relationships through every level of the chain.

### Employees Without Reports

Leaf employees have no descendants. Aggregation queries naturally produce no matching rows for them. The final `LEFT JOIN` combined with `COALESCE` ensures these employees still appear in the output with team size `0` and budget equal to their own salary.

### Large Organizational Trees

In large organizations, managers may control hundreds or thousands of indirect reports. The recursive ancestor-descendant expansion ensures every reporting relationship is captured exactly once, allowing team size and budget calculations to remain accurate regardless of hierarchy depth or breadth.