LeetCode 3236 - CEO Subordinate Hierarchy

This problem requires building a hierarchical view of a company's employee structure starting from the CEO. The Employees table contains employee records, including their unique ID, name, manager ID, and salary. The CEO is identified as the employee with a NULL managerid.

leetcodeharddatabase

LeetCode Problem 3236

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

This problem requires building a hierarchical view of a company's employee structure starting from the CEO. The Employees table contains employee records, including their unique ID, name, manager ID, and salary. The CEO is identified as the employee with a NULL manager_id.

The task is to return all subordinates of the CEO, both direct and indirect, along with two additional pieces of information: their level in the hierarchy (where direct reports are level 1, their reports are level 2, and so on) and the difference between their salary and the CEO's salary. The output must be sorted first by hierarchy_level ascending, then by subordinate_id ascending.

The input represents a tree-like hierarchy with a single root (the CEO) and branches representing management chains. Each employee has exactly one manager except the CEO. Edge cases to consider include employees with no subordinates, employees who are deep in the hierarchy, and scenarios where salaries are equal to the CEO.

The main constraints indicate that the table can have multiple levels but forms a proper tree structure with no cycles. This makes recursive traversal possible.

Approaches

A brute-force approach would involve repeatedly scanning the table to find employees reporting to a given manager, iterating level by level until all subordinates are found. This approach works but is inefficient, especially for deep hierarchies, because each level requires a full table scan.

The optimal approach leverages a recursive common table expression (CTE), which allows hierarchical traversal in SQL. Starting with the CEO, we recursively find all employees reporting to the current set of managers, incrementing the hierarchy level and calculating the salary difference on the fly. This approach is efficient because it avoids repeated table scans and exploits the database engine's recursion optimization.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Iteratively scans the table for each level of the hierarchy
Optimal O(n) O(n) Recursive CTE finds all subordinates in a single query pass

Algorithm Walkthrough

  1. Identify the CEO: Query the Employees table to find the employee with manager_id IS NULL. This employee is the root of the hierarchy. Store their employee_id and salary.
  2. Initialize the recursive CTE: Start the CTE with all employees whose manager_id matches the CEO’s employee_id. Assign hierarchy_level = 1 and calculate the salary_difference as subordinate salary minus CEO salary.
  3. Recursive step: For each employee found in the previous step, recursively find all employees whose manager_id matches any employee in the current set. Increment hierarchy_level by 1 and calculate the new salary_difference.
  4. Continue recursion until no more subordinates are found.
  5. Final selection and ordering: Select all rows from the recursive CTE and order by hierarchy_level ascending, then subordinate_id ascending.

Why it works: The recursive CTE expands the hierarchy level by level, ensuring every subordinate is included exactly once, with the correct level and salary difference relative to the CEO. Ordering ensures that the output matches the problem requirement.

Python Solution

import sqlite3

def ceo_subordinates(conn: sqlite3.Connection):
    query = """
    WITH RECURSIVE Subordinates AS (
        SELECT 
            employee_id AS subordinate_id,
            employee_name AS subordinate_name,
            1 AS hierarchy_level,
            salary - (SELECT salary FROM Employees WHERE manager_id IS NULL) AS salary_difference
        FROM Employees
        WHERE manager_id = (SELECT employee_id FROM Employees WHERE manager_id IS NULL)
        
        UNION ALL
        
        SELECT 
            e.employee_id,
            e.employee_name,
            s.hierarchy_level + 1,
            e.salary - (SELECT salary FROM Employees WHERE manager_id IS NULL)
        FROM Employees e
        INNER JOIN Subordinates s ON e.manager_id = s.subordinate_id
    )
    SELECT *
    FROM Subordinates
    ORDER BY hierarchy_level ASC, subordinate_id ASC;
    """
    cur = conn.cursor()
    cur.execute(query)
    return cur.fetchall()

The Python implementation uses SQLite’s recursive CTE to traverse the employee hierarchy. The CEO is identified in a subquery. The recursion ensures that each employee’s hierarchy level and salary difference are correctly calculated relative to the CEO. The final result is fetched and returned as a list of tuples.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
    "log"
)

type Subordinate struct {
    SubordinateID   int
    SubordinateName string
    HierarchyLevel  int
    SalaryDifference int
}

func ceoSubordinates(db *sql.DB) ([]Subordinate, error) {
    query := `
    WITH RECURSIVE Subordinates AS (
        SELECT 
            employee_id AS subordinate_id,
            employee_name AS subordinate_name,
            1 AS hierarchy_level,
            salary - (SELECT salary FROM Employees WHERE manager_id IS NULL) AS salary_difference
        FROM Employees
        WHERE manager_id = (SELECT employee_id FROM Employees WHERE manager_id IS NULL)
        
        UNION ALL
        
        SELECT 
            e.employee_id,
            e.employee_name,
            s.hierarchy_level + 1,
            e.salary - (SELECT salary FROM Employees WHERE manager_id IS NULL)
        FROM Employees e
        INNER JOIN Subordinates s ON e.manager_id = s.subordinate_id
    )
    SELECT subordinate_id, subordinate_name, hierarchy_level, salary_difference
    FROM Subordinates
    ORDER BY hierarchy_level ASC, subordinate_id ASC;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results []Subordinate
    for rows.Next() {
        var s Subordinate
        err := rows.Scan(&s.SubordinateID, &s.SubordinateName, &s.HierarchyLevel, &s.SalaryDifference)
        if err != nil {
            return nil, err
        }
        results = append(results, s)
    }
    return results, nil
}

The Go solution mirrors the Python version. Differences include the explicit struct definition for the result and handling of sql.Rows with proper error checking. SQLite’s recursive CTE works identically, and the Go code collects results into a slice.

Worked Examples

Using the example Employees table:

Step Current Subordinates Hierarchy Level Salary Difference
Initial Bob, Charlie 1 -30000, -40000
Recursive 1 David, Eve, Frank, Grace 2 -45000, -50000, -55000, -52000
Recursive 2 Helen 3 -60000

At each recursion, the algorithm finds all employees reporting to the current set of subordinates, increments the hierarchy level, and calculates the salary difference. Final ordering by hierarchy level and subordinate ID gives the output as required.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each employee is visited exactly once in the recursive CTE
Space O(n) Storing the recursive CTE result requires space proportional to the number of employees

This linear complexity is optimal given that every employee must be output exactly once.

Test Cases

# provided example
assert ceo_subordinates(conn) == [
    (2, "Bob", 1, -30000),
    (3, "Charlie", 1, -40000),
    (4, "David", 2, -45000),
    (5, "Eve", 2, -50000),
    (6, "Frank", 2, -55000),
    (7, "Grace", 2, -52000),
    (8, "Helen", 3, -60000),
]

# single employee (CEO only)
assert ceo_subordinates(conn_single_ceo) == []

# all employees report directly to CEO
assert ceo_subordinates(conn_flat) == [
    (2, "Bob", 1, -5000),
    (3, "Charlie", 1, -3000),
]

# deep hierarchy
assert ceo_subordinates(conn_deep) == [
    (2, "A", 1, -1000),
    (3, "B", 2, -2000),
    (4, "C", 3, -3000),
]
Test Why
Provided example Validates normal hierarchy with multiple levels
Single employee Ensures function handles no subordinates
Flat hierarchy Tests all direct reports to CEO
Deep hierarchy Tests multiple levels and recursion correctness

Edge Cases

One important edge case is when the CEO has no subordinates. The recursive CTE returns an empty set, which must not produce errors. Another edge case is a very deep hierarchy, where recursion depth could become large. The implementation handles this efficiently because SQL recursion is optimized and controlled by the database engine. A third edge case is when some employees have salaries equal to the CEO, resulting in a zero salary difference; this is correctly calculated because the salary difference formula subtracts the CEO salary from each subordinate's salary. These edge cases validate that the solution works for minimal, maximal, and boundary conditions.