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!

What have you tried and what did not work? Walking over a tree is pretty standard task... so it is a bit unclear what is the problem right now. — Alexei Levenkov, Jun 26 '12 at 01:17

Blueberry · Accepted Answer · 2012-06-26T01:35:27.090

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);
}

That doesn't help me find all the children though - it would only get one level of children. — Marcus, Jun 26 '12 at 01:25
That works a treat. Thanks so much and it makes a lot of sense :) — Marcus, Jun 26 '12 at 01:53

score 1 · Answer 2 · answered Oct 15 '14 at 06:38

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;
}

How do I get all children from a given parent node?

2 Answers2

Linked