Python: dict of dicts (tree) into a list

Question

I have a dict of dicts that represents a tree:

{1: {2: 3, 4: 5}, 6: {7: 8, 9: 10}}

How can I turn it into all possible paths from the root to its leaves?

The otput should be smt like this:

[[1,2,3],[1,4,5],[6,7,8],[6,9,10]]

Is there some kind of Python dict comprehension moneliner that can solve this problem for any dict depth?

You might want to consider using [recursion](http://stackoverflow.com/questions/30214531/basics-of-recursion-in-python) — LMc, Nov 11 '16 at 20:39
One typically looks for one-liners after coming with a multi-line solution. — Scott Hunter, Nov 11 '16 at 20:41
*dict comprehension moneliner* and *any dict depth* sounds conflicting — RomanPerekhrest, Nov 11 '16 at 21:08

score 6 · Accepted Answer · answered Nov 11 '16 at 20:40

This is what recursion is perfect for:

def paths(tree):
    if not isinstance(tree, dict):
        return [[tree]]
    return [[key] + path
            for key, value in tree.items()
            for path in paths(value)]

print(paths({1: {2: 3, 4: 5}, 6: {7: 8, 9: {10: 11, 12: 13}}}))

Output:

[[1, 2, 3], [1, 4, 5], [6, 9, 10, 11], [6, 9, 12, 13], [6, 7, 8]]

Python: dict of dicts (tree) into a list

1 Answers1