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

Question

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.

Answer 1

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.

Answer 2

You can use something like this, similar to the selected answer.

 import collections

 def iter_paths(tree, parent_path=()):
     for path, node in tree.iteritems():
         current_path = parent_path + (path,)
         if isinstance(node, collections.Mapping):
             for inner_path in iter_paths(node, current_path):
                 yield inner_path
         else:
             yield current_path

For the following dict:

tree = {'A':1, 'B':{'B1':1, 'B2':2}, 'C':{'C1':{'C11':1, 'C12':2},'C2':{'C21':1, 'C22':2}}}

The output should be (the yield order may be different):

('A',)
('C', 'C2', 'C22')
('C', 'C2', 'C21')
('C', 'C1', 'C12')
('C', 'C1', 'C11')
('B', 'B1')
('B', 'B2')

Answer 3

Assuming tree structure is of this format: {'0': {'A': {}, 'B': {}}} then something like this should do the trick.

def paths(nodeId, children, ancestors, allPaths):
    ancestors.append(nodeId)
    if len(children) == 0:
        allPaths.append(ancestors)
    else:
        for childId in children:
            paths(childId, children[childId], ancestors[:], allPaths)

allPaths = []
paths('0', tree['0'], [], allPaths)

Something like that should work. Normally i would try this out first, but i'm on my iPad right now. If it doesn't work, it should give you some ideas.