How to find path from a given node to all leaf nodes in python

Question

I have a dictionary which has list of parent and child node associated with each node (dictionary reference in code). I will input one key (For following piece of code B is the key). I have to keep parent node into consideration. For B I want paths as [B,C,C1,X],[B,C,C2],[B,D,D1],[B,D,D2].

The output for the following piece of code that I obtain is :

C ['C1', 'C2']

C1 ['X']

Also I get the following error:

File "", line 7, in path_find if d[i]['parent'] == [key]:

KeyError: 'X'

def path_find(graph,key):

    x = d[key]['child'] 
    for i in x:
        if d[i]['parent'] == [key]:
            print(i,d[i]['child'])
            path_find(d,i)


d = {'B':{
 'parent' : ['A'],
  'child': ['C','D']},
'C':{
'parent' : ['B'],
'child' : ['C1','C2']},
        'D':{
 'parent' : ['B'],
  'child': ['D1','D2']},
    'C1':{
            'parent' : ['C'],
            'child': ['X']}}

key = 'B'
path_find(d,key)

The expected output is : [B, C, C1, X], [B, C, C2], [B, D, D1], [B, D, D2]

actual output is :

C ['C1', 'C2']

C1 ['X']

Answer 1

There are few errors in your code:

1) You didn't add info about X node in your d = { ... }, that's why you got KeyError. I suppose it's a node without children.

2) You didn't save paths to current node so your output is invalid.

Corrected code (with my comments):

def path_find(graph, key, current_path, paths_list):  # graph, current node key, path to current node, all paths list
    if key not in d: # not in graph - no children
        paths_list.append(current_path)
        return
    children = d[key]['child'] 
    for child in children:  # check all children
        path_find(graph, child, current_path[:] + [child], paths_list)
    if not children:  # no children - finish search
        paths_list.append(current_path)


d = {'B':{
 'parent' : ['A'],
  'child': ['C','D']},
'C':{
'parent' : ['B'],
'child' : ['C1','C2']},
        'D':{
 'parent' : ['B'],
  'child': ['D1','D2']},
    'C1':{
            'parent' : ['C'],
            'child': ['X']}}

key = 'B'
paths_list = []
path_find(d, key, [key], paths_list)
print(paths_list)

Output:

[['B', 'C', 'C1', 'X'], ['B', 'C', 'C2'], ['B', 'D', 'D1'], ['B', 'D', 'D2']]