How to print all possible paths of a binary tree given that I have all directly connected nodes as a list in a dictionary?

user_11289239 0
Viewed 382

I have a tree with nodes: [1,2,3,4,5] with 1 as root. Can be represented as:

enter image description here

And I have a dictionary having keys as nodes and they contain a list of nodes connected to them,

my_dict = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}

From this dictionary I want to print all the paths possible from the root to leaf nodes as a list like:

output: [[1,2,4],[1,2,5],[1,3]]

What I have tried is,

l = list()
root = 1
def path_finder(root):
    l.append(root)
    prev = root
    for val in my_dict[root]:
        print(val)
        path_finder(val)
        if root == prev:
            print("End of path")

Which returns: 

2
4
End of path
5
End of path
End of path
3
End of path

I am completely stuck at this, any help will be highly appreciated. Thanks in advance :-)

binary-tree tree recursion python-3.x python
1 Answers

You can use a recursive generator:

my_dict = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}
def get_paths(s, c = []):
  if not my_dict[s]:
     yield c+[s]
  else:
     for i in my_dict[s]:
       yield from get_paths(i, c+[s])

print(list(get_paths(1)))

Output:

[[1, 2, 4], [1, 2, 5], [1, 3]]
user_73267380
Related