Generate all leaf-to-root paths in a dictionary tree in Python

python, recursion, tree

Solution

Assuming you actually intended the following structure for `tree`:

tree = {'0': {'A': {'B': {'C': {}}},
              'D': {'E': {},
                    'F': {}}}}

Here is a similar `paths()` function that should do what you want:

def paths(tree, cur=()):
    if not tree:
        yield cur
    else:
        for n, s in tree.items():
            for path in paths(s, cur+(n,)):
                yield path

Result:

>>> list(paths(tree))
[('0', 'A', 'B', 'C'), ('0', 'D', 'E'), ('0', 'D', 'F')]

Note that I used a tuple as the default argument instead of a list, this is because mutable default arguments can get you into trouble.

Problem

I have a dictionary-tree in an "non-standard" form like so: ``` tree = {'0': {'A': {'B': {'C': {}}}}, {'D': {'E': {}}, {'F': {}}}} ``` Leaf nodes are defined as dictionary key-value pairs where the values is an empty dictionary. I would like to extract all the leaf-to-root paths as lists of lists like so: ``` paths_ = [['C', 'B', 'A', '0'], ['E', 'D', '0'], ['F', 'D', '0']] ``` The paths can be reversed too if that is helpful. ``` paths_ = [['0', 'A', 'B', 'C'], ['0', 'D', 'E'], ['0', 'D', 'F']] ``` I know I have to do it recursively and I need an accumulator list for each path. It would also be nice if the function yielded the path-lists. What I have so far is this: ``` def paths(node, subtree, acc=[]): if not subtree: yield [node]+acc for n, s in subtree.items(): yield paths(n, s, acc) ``` It doesn't really do what I want: ``` paths_ = list(paths('0', tree['0'])) ``` Ideally this should return the list-of-lists. Any help will be much appreciated.

Original source

Related problems