How do I get all children from a given parent node

Question

I have a list of parent/child IDs and would like to get all child IDs for a given parent ID. There are no null parents (the top level IDs don't appear as child IDs).

Currently the parent/child IDs are recorded as a KeyValuePair in a list, however this could be easily changed to another data structure if that would be better:

List<KeyValuePair<int, int>> groups = new List<KeyValuePair<int, int>>();
groups.Add(new KeyValuePair<int,int>(parentID, childID));

For example, here are sample parent/children. The children of parent 27 would be 5944, 2065, 2066, 2067, 6248, 6249, 6250.

Parent  Child
27      1888
1888    5943
1888    5944
5943    2064
5943    2065
5943    2066
5943    2067
2064    6248
2064    6249
2064    6250

Any help would be greatly appreciated!

Answer 1

Why dont you change the type of Dictionary<int, List<int>>, where the parent is the key and the value (list of ints) is the children?

Then you would get back the list of children using:

    private List<int> GetAllChildren(int parent)
    {
        List<int> children = new List<int>();
        PopulateChildren(parent, children);
        return children;
    }

    private void PopulateChildren(int parent, List<int> children)
    {
        List<int> myChildren;
        if (myitems.TryGetValue(parent, out myChildren))
        {
            children.AddRange(myChildren);
            foreach (int child in myChildren)
            {
                PopulateChildren(child, children);
            }
        }
    }

You will need to weight out the performance impact as this will speed up reads and slow down writes (a huge majority of the time nobody would even notice).

You will also need to check if the list is in the dictionary using myitems.TryGet(...) and if not, you will need to create it, but this is o(1), so is practically instant.

private static void AddEntry(int parent, int child)
{
    List<int> children;
    if (!myitems.TryGetValue(parent, out children))
    {
        children = new List<int>();
        myitems[parent] = children;
    }
    children.Add(child);
}

Answer 2

Its simple. Just think that you have the list in the following array

    List<KeyValuePair<int, int>> groups = new List<KeyValuePair<int, int>>();
    groups.Add(new KeyValuePair<int, int>(27, 1888));
    groups.Add(new KeyValuePair<int, int>(1888, 5943));
    groups.Add(new KeyValuePair<int, int>(1888, 5944));
    groups.Add(new KeyValuePair<int, int>(5943, 2064));
    groups.Add(new KeyValuePair<int, int>(5943, 2065));
    groups.Add(new KeyValuePair<int, int>(5943, 2066));
    groups.Add(new KeyValuePair<int, int>(5943, 2067));
    groups.Add(new KeyValuePair<int, int>(2064, 6248));
    groups.Add(new KeyValuePair<int, int>(2064, 6249));
    groups.Add(new KeyValuePair<int, int>(2064, 6250));
    groups.Add(new KeyValuePair<int, int>(2000, 1000));
    // Pass the 1st parameter as the parent to get all children
    List<int> childs = GetAllChild(27, groups);

You need to use a "Recursive function" to get children dynamically. Just call the following method to get all children of a parent

public List<int> GetAllChild(int id,List<KeyValuePair<int, int>> newLst)
{
      List<int> list = new List<int>();
      for (int i = 0; i < newLst.Count; i++)
      {
            if (Convert.ToInt32(newLst[i].Key) == id)
            {
                 if (!list.Contains(Convert.ToInt32(newLst[i].Value)))
                 {
                     list.Add(Convert.ToInt32(newLst[i].Value));
                     List<int> l = GetAllChild(newLst[i].Value, newLst);
                     list.AddRange(l);
                 }
            }
       }
       return list;
}