How to get the list of employees and their reporting level recursively using LINQ

Question

I have a table for list of employees with their supervisors.

| UserID | SupervisorUserId |
|--------|------------------|
| 10     | null             |
| 1      | 10               |
| 2      | 1                |
| 3      | 1                |
| 4      | 3                |
| 5      | 10               |
| 6      | 5                |
| 7      | 6                |
| 8      | 6                |
| 9      | 8                |

Here's a diagram for visualisation:

And here's what I have right now:

public JsonResult GetEmployeesWithReportingLevel()
{
    try
    {

        var getEmployees = GetEmployees().ToList();

        var employeeList = (from e in getEmployees
                            where e.IsDeleted != true
                            select new ReportingLineList
                            {
                                UserId = e.UserId,
                                SupervisorId = e.SupervisorId 
                            }).ToList();

        var reportingLevel = (from emp in employeeList
                                select new 
                                {
                                    UserId = emp.UserId,
                                    ReportingLevel = GetReportingLevel(employeeList, emp.UserId, 0)
                                }).ToList();

        return new JsonResult(reportingLevel);
    }
    catch
    {
        throw;
    }
}

private int GetReportingLevel(IEnumerable<ReportingLineList> employeeList, Guid UserId, int reportingLevel)
{
    try
    {
        var reportingEmployees = (from emp in employeeList
                                        where emp.SupervisorId == UserId
                                        select new 
                                        {
                                            UserId = emp.UserId
                                        }).ToList();

        foreach (var emp in reportingEmployees)
        {
            if (emp.UserId != null)
            {
                return GetReportingLevel(employeeList, (Guid)emp.UserId, reportingLevel + 1);
            }
        }

        return reportingLevel;
    }
    catch
    {
        throw;
    }
}

My expected result should be:

| UserId | Reporting level |
|--------|-----------------|
| 2      | 0               |
| 4      | 0               |
| 7      | 0               |
| 9      | 0               |
| 3      | 1               |
| 8      | 1               |
| 1      | 2               |
| 6      | 3               |
| 5      | 3               |
| 10     | 4               |

With my current result, it seems like it is just iterating with the first employee that my code will get.

Here's the result that I'm getting.

| UserId | Reporting level |
|--------|-----------------|
| 2      | 0               |
| 4      | 0               |
| 7      | 0               |
| 9      | 0               |
| 3      | 1               |
| 8      | 1               |
| 1      | 1               |
| 6      | 1               |
| 5      | 2               |
| 10     | 3               |

Answer 1

So I am kinda new also, but it seems like your problem can just be fixed by adding an .OrderBy() if I'm not mistaken.

Here is a link to check it out: MSDN Enumerable.OrderBy Method

Answer 2

I think you could simplify your recursion method. Passing a reporting level as an input parameter should not be necessary.

Considering the expected output you have provided for the example input and associated diagram, I'd say the implementation logic can be put into words as follows:

1. If no one is reporting to employee X, then employee X has reporting level 0
2. Otherwise, employee X's reporting level is one higher than the highest reporting level of all employees that are reporting directly to employee X

From how I interpret your current implementation of GetReportingLevel(), I believe you are addressing the first statement and most of the second statement, but missing the the highest part of one higher than the highest reporting level of all employees that are reporting directly to employee X in the second statement.

In pseudocode, I would reflect the logic in the two statements as as follows in the recursion method:

int GetReportingLevel(<all employees>, <employee / user ID>)
{
    // Find all the employees in <all employees> that report directly to <employee>

    // If no employees report directly to <employee>:
    // return 0

    // Otherwise:
    // return 1
    //    + the maximum reporting level of all employees that report directly to <employee>
}

I'll refer to all the employees that report directly to <employee> as the subordinates of <employee>.

A rather straight-forward implementation of this pseudocode is:

private static int GetReportingLevel(IEnumerable<ReportingLineList> employeeList, int userId)
{
    var subordinates = employeeList
        .Where(emp => emp.SupervisorUserId == userId);
    
    if (!subordinates.Any())
    {
        return 0;
    }
    
    return 1 + subordinates.Max(sub => GetReportingLevel(employeeList, sub.UserId));
}

Example fiddle for the straight-forward approach here.

---

In the straight-forward implementation, though, you will basically traverse the whole subtree of an employee and calculate the reporting levels of all of the employee's descendants to be able to calculate the one employee's reporting level, even if you have already traversed part of the subtree (or even the whole subtree!) beforehand during the calculation of another employee's reporting level.

To provide an example, I'll borrow your diagram:

If you start by calculating the reporting level of Emp 10, you will traverse the whole tree just to calculate the reporting level of Emp 10 (blue area), seeing as the reporting levels are computed from the leaf nodes and upwards. When you then move on to calculate the reporting level of Emp 1, you will redo a subset of all the recursive calls that were just made when calculating the reporting level of Emp 10 (orange area).

We want to minimize the amount of recursive calls whenever we have the chance. I'd suggest using a dictionary to keep track of which reporting levels we have already calculated, and simply getting the reporting level from the dictionary whenever we need it and it has already been calculated.

The pseudocode for such an implementation could be:

// dictionary with key <user ID> and value <reporting level>

int GetReportingLevel(<all employees>, <employee / user ID>)
{
    // If my dictionary already has an entry for <employee>:
    // return the reporting level from the dictionary

    // Otherwise: Find all the employees in <all employees>
    //    that report directly to <employee>

    // Calculate the reporting level for <employee>
    //    (using the same logic as in the straight-forward implementation)
    //    and add <employee's user ID> and their reporting level to the dictionary

    // return the reporting level that was just calculated for <employee>
}

The implementation may look like:

private static Dictionary<int, int> _reportingLevelForUserId = new();

private static int GetReportingLevel(IEnumerable<ReportingLineList> employeeList, int userId)
{
    if (_reportingLevelForUserId.TryGetValue(userId, out var reportingLevel))
    {
        return reportingLevel;
    }
    
    var subordinates = employeeList
        .Where(emp => emp.SupervisorUserId == userId);
    
    _reportingLevelForUserId[userId] = subordinates.Any()
        ? 1 + subordinates.Max(sub => GetReportingLevel(employeeList, sub.UserId))
        : 0;
    
    return _reportingLevelForUserId[userId];
}

Example fiddle for the more optimized approach here.

---

For the example input you have provided, the straight-forward approach results in 31 calls to GetReportingLevel(), whereas the dictionary-based approach results in 19 calls to GetReportingLevel(). For such a small tree, it may not make much of a difference; but the larger the tree, the more important such an optimization is.

In both of the implementations of GetReportingLevel(), I have assumed the following structure of the ReportingLineList class:

public class ReportingLineList
{
    public int UserId { get; set; }
    public int? SupervisorUserId { get; set; }
}

If the output is calucated as follows:

var employeesWithReportingLevel = employeeList
    .Select(employee => new
        {
            UserId = employee.UserId,
            ReportingLevel = GetReportingLevel(employeeList, employee.UserId)
        })
    .OrderBy(reportingEmployee => reportingEmployee.ReportingLevel)
    .ToList();

, either implementation of the method generates the following output for the given input:

           Input                               Output
=============================        ===========================
                             
| UserID | SupervisorUserId |        | UserId | ReportingLevel |
|--------|------------------|        |--------|----------------|
|     10 |             null |        |      2 |              0 |
|      1 |               10 |        |      4 |              0 |
|      2 |                1 |        |      7 |              0 |
|      3 |                1 |        |      9 |              0 |
|      4 |                3 |        |      3 |              1 |
|      5 |               10 |        |      8 |              1 |
|      6 |                5 |        |      1 |              2 |
|      7 |                6 |        |      6 |              2 |
|      8 |                6 |        |      5 |              3 |
|      9 |                8 |        |     10 |              4 |