pythonrecursionparent-childgrandchild

How to get the list of children and grandchildren from a nested structure?


Given this dictionary of parent-children relations,

{
    2: [8, 7],
    8: [9, 10],
    10: [11],
    15: [16, 17],
}

I'd like to get the list of all children, grandchildren, great-grandchildren, etc. -- e.g. given a parent with an ID 2 I want to get the following list: [8, 7, 9, 10, 11]. The number of nesting levels can be infinitely long. Cycles are not possible.

So far I was able to achieve this function but I don't know how to return from it:

links = {
    2: [8, 7],
    8: [9, 10],
    10: [11],
    15: [16, 17],
}

def get_nested_children(parent_uid, acc = []):
    if parent_uid in links:
        acc = acc + links[parent_uid]
        print("[in loop]", acc)

        for child_uid in links[parent_uid]:
            get_nested_children(child_uid, acc)
    else:
        return acc

print(get_nested_children(2))

Which outputs:

[in loop] [8, 7]
[in loop] [8, 7, 9, 10]
[in loop] [8, 7, 9, 10, 11]
None

Solution

  • Since cycles aren't possible and the order is not important, the easiest way to do this is with a generator function. Just yield the children and yield from the results of recursion. This will give you a depth first result:

    links = {
        2: [8, 7],
        8: [9, 10],
        10: [11],
        15: [16, 17],
    }
    
    def get_nested_children(parent_uid):
            for child_uid in links.get(parent_uid, []):
                yield child_uid
                yield from get_nested_children(child_uid)
    
    
    list(get_nested_children(2))
    # [8, 9, 10, 11, 7]
    

    If you want a traditional function you can just append each child, then extend the results of recursion onto a local list, which you can return:

    def get_nested_children(parent_uid):
            res = []
            for child_uid in links.get(parent_uid, []):
                res.append(child_uid)
                res.extend(get_nested_children(child_uid))
            return res
    
    
    get_nested_children(2)
    # [8, 9, 10, 11, 7]