CODEWITHSUNDEEP
c#linqrecursion
John Ohara
John Ohara

Reputation: 2901

List of descendant ID - children, grandchildren etc

CREATE TABLE [dbo].[Topic] (
    [Id]          SMALLINT      NOT NULL,
    [ParentId]    SMALLINT      NULL
);

I have a simple table (above) with a parent/child hierarchy. I'm using Entity Framework to extract the data. The number of rows is less than 100.

I want to get a list of descendant ID, consisting of the children, grandchildren and so on (possibly with the option of including the original root parent). As the table only contains a small number of rows, it's probably easier to extract all the data to a List<Topic> first and work on that, but I stand to be corrected.

The preferred output would be: Dictionary<int, List<int>>

Where the key would be the ID and the list would contain child/grandchild ID's

I've looked at tens and tens of solutions online but I can't find a solution that meets my needs. Can anyone help?

Upvotes: 1

Views: 433

Answers (2)

Svyatoslav Danyliv
Svyatoslav Danyliv

Reputation: 27282

Consider that result has to be stored in tree:

public class TopicModel
{
    public int Id { get; set; }
    public int? ParentId{ get; set; }
    public List<TopicModel> Children { get; set; };
}

Building tree:

// retrieveing from database
var plainResult = context.Topic
    .Select(t => new TopicModel 
    { 
        Id = x.Id
        ParentId = x.ParentId
    })
    .ToList();

var lookup = plainResult.Where(x => x.ParentId != null).ToLookup(x => x.ParentId);

foreach (c in plainResult)
{
    if (lookup.Contains(c.Id))
    {
        c.Children = lookup[c.Id].ToList();
    }
}

// here we have all root items with children intialized 
var rootItems = plainResult.Where(x => x.ParentId == null).ToList();

And searching for children:

public static IEnumerable<TopicModel> GetAllChildren(TopicModel model)
{
    if (model.Children != null)
    {
        foreach (var c in model.Children)
        {
            yield return c;

            foreach (sc in GetAllChildren(c))
                yield return sc;
        }
    }
}

Upvotes: 2

Mathias R. Jessen
Mathias R. Jessen

Reputation: 174485

You could populate a dictionary with the ParentId->Id relations and use that to resolve sub-topics:

// prepare dictionary
var dictionary = new Dictionary<short, List<Topic>>();

// in real life this would get replaced by your database query
var topics = new List<Topic>
{
    new Topic { Id = 1 },
    new Topic { Id = 2, ParentId = 1 },
    new Topic { Id = 3, ParentId = 1 },
    new Topic { Id = 4, ParentId = 1 },
    new Topic { Id = 5, ParentId = 1 },
    new Topic { Id = 6, ParentId = 2 },
    new Topic { Id = 7, ParentId = 2 },
    new Topic { Id = 8, ParentId = 3 },
    new Topic { Id = 9, ParentId = 4 },
    new Topic { Id = 10, ParentId = 4 },
    new Topic { Id = 11, ParentId = 8 },
    new Topic { Id = 12, ParentId = 8 }
};

// populate dictionary with relations from DB
foreach(var topic in topics)
{
    var key = topic.ParentId ?? -1;
    if(!dictionary.ContainsKey(key))
    {
        dictionary.Add(key, new List<Topic>());
    }

    dictionary[key].Add(topic);
}

Now that you have the mappings available, you can write a simple recursive iterator method to resolve the descendants of a given id:

IEnumerable<short> GetDescendantIDs(short from)
{
    if(dictionary.ContainsKey(from))
    {
        foreach(var topic in dictionary[from])
        {
            yield return topic.Id;
            foreach(var child in GetDescendants(topic.Id))
                yield return child;
        }
    }
}

// resolves to [1, 2, 6, 7, 3, 8, 11, 12, 4, 9, 10, 5]
var descendantsOfRoot = GetDescendantIDs(-1);

// resolves to [8, 11, 12]
var descendantsOfThree = GetDescendantIDs(3);

The Topic class used in the example above is just:

class Topic
{
    internal short Id { get; set; }
    internal short? ParentId { get; set; }
}

Upvotes: 3

Related Questions