Tree branch algorithm

Question

I'm trying to make a function where the input is a list of IDs and output is a tree with the nodes based on their ID and all parent nodes.

Each node has a ParentID. Home (ID: 1) is the root.

The function header would be something like:

public ModuleDTO GetModuleTree(List<int> ids);

Sample tree would be the following:

• 1 Home
  • 2 Applications
  • 3 Teaching
    • 4 Courses
    • 5 Rooms
    • 6 Teachers
  • 7 Research
    • 8 Publications
  • 9 Graduation

If 4 is passed to the function, it would return a tree like this:

• 1 Home
  • 3 Teaching
    • 4 Courses

If 5 and 8 are passed to the function, it would return a tree like this:

• 1 Home
  • 3 Teaching
    • 5 Rooms
  • 7 Research
    • 8 Publications

If 3 is passed to the function, it would return a tree like this:

• 1 Home
  • 3 Teaching

My class is the following:

public class ModuleDTO
{
    public int ID { get; set; }
    public string Name { get; set; }
    public string TitleIS { get; set; }
    public string TitleEN { get; set; }
    public string RootURL { get; set; }
    public int? ParentID { get; set; }
    public List<ModuleDTO> ChildModules { get; set; }

    public ModuleDTO()
    {
        ChildModules = new List<ModuleDTO>();
    }
}

Thanks in advance.

Answer 1

(I will assume that lookup speed is not of great importance here, or that the trees are moderately small)

First let's think about finding the answer for a single input. A usable approach here would be to try a depth-first type algorithm, a recursive algorithm. Look at every node in your tree, and as soon as you've found it, return it. As soon as you start returning from your recursion, you will continue "up" the tree, and return all the nodes along the way to the home node.

The case with several ids then becomes just doing this several times, and joining all the results.

There are of course several improvements that can be made to this algorithm, as well as other approaches that can be taken, depending on performance needs and freedom to change data structures. They might not be quite as simple and clear as an implementation of the above solution, though.

Answer 2

I solved it with this:

public ModuleDTO GetModulesForUser(string userName)
{
    // Returns the list of IDs
    var ids = ListOfUserModules(userName);

    var modules = GetModuleTree(null);
    var module = modules.First();

    PruneTree(module, ids);

    return module;
}

public List<ModuleDTO> GetModuleTree(ModuleDTO parentModule)
{
    int? parentID = null;

    if (parentModule != null)
    {
        parentID = parentModule.ID;
    }

    var childModules = _modules.All().Where(s => s.ParentID == parentID).Select(x => x.ToDTO());

    List<ModuleDTO> modules = new List<ModuleDTO>();

    foreach (var m in childModules)
    {
        m.ChildModules = GetModuleTree(m);
        modules.Add(m);
    }

    return modules;
}

private void PruneTree(ModuleDTO root, List<int> ids)
{
    for(int i = root.ChildModules.Count() - 1; i >= 0; i--)
    {
        PruneTree(root.ChildModules[i], ids);
        if (root.ChildModules[i].ChildModules.Count == 0)
        {
            if (!ids.Contains(root.ChildModules[i].ID))
            {
                root.ChildModules.RemoveAt(i);
            }
        }
    }
}