python - Recurse through dictionary of dictionaries, always starting from the top -

i have dictionary of following, of unknown hierarchical depth:

dict_of_dicts = {'a': {'b': {'c': {}, 'd': {}, 'e': {}}}, 'f': {'g': {}}} 

i found the following useful learning how recurse this, have had trouble modifying code want, list of paths top hierarchal level dead ends.

the desired output is:

list = ['a,b,c', 'a,b,d', 'a,b,e', 'f,g'] 

to start approaching this, used dfs approach:

hierarchy = [] parent in dict_of_dicts:     recurse_dicts(concepts, parent, hierarchy)  def recurse_dicts(concepts, parent, hierarchy):     hierarchy.append(parent)     child in concepts[parents]:         if len(recurse[node][child].keys()) > 0:             recurse_dicts(recurse[node], child, hierarchy)         else:             return 

this resulted in:

hierarchy = ['a', 'b', 'c', 'd', 'e'] 

which something, not quite wanted.

assuming values always dictionaries, use:

def paths(d, path=(), res=none):     if res none:         res = []     key, value in d.iteritems():         if not value:             # end of line, produce path             res.append(','.join(path + (key,)))         else:             # recurse down find end of path             paths(value, path + (key,), res)     return res 

this uses shared list (produced on first call) pass resulting generated paths caller, , builds path each recursion step, add result list whenever empty value encountered.

demo:

>>> dict_of_dicts = {'a': {'b': {'c': {}, 'd': {}, 'e': {}}}, 'f': {'g': {}}} >>> paths(dict_of_dicts) ['a,b,c', 'a,b,e', 'a,b,d', 'f,g'] 

the paths not sorted, because dictionaries have no order; can still sort on keys if desired:

for key in sorted(d):     value = d[key] 

instead of for key, value in d.iteritems() loop.