Dictionary graph to list by breadth-first order

Question

I have the following graph (which is in this case is a binary tree) as a dictionary.

G = {
    'root': ['4', '3'],
    '4': ['2', 'a'],
    '3': ['1', 'd'],
    '2': ['b', 'e'],
    '1': ['f', 'c']
    }

And i want a function that returns the list representation in breadth-first order, which would be as follows:

arr = ['root','4','3','2','a','1','d','b','e',None,None,'f','c',None,None ]

If what I want to achieve is not clear please tell me and I will give more info :)

What I had in mind so far, was to read the root element from the dict, and then get the children nodes, then read each children, at the same time pushing each of those to a list, but it's kinda confusing and I'd appreciate some help.

Answer 1

I don't think your expected output is correct. There are 6 leaf nodes, each with two None child nodes, and yet you only have 4 Nones in your expected output rather than 12.

With the following code:

from collections import deque
def bf(tree, node='root'):
    output = []
    queue = deque([node])
    while queue:
        node = queue.popleft()
        output.append(node)
        if node is not None:
            for i in tree.get(node, [None, None]):
                queue.append(i)
    return output
print(bf(G))

It would output:

['root', '4', '3', '2', 'a', '1', 'd', 'b', 'e', None, None, 'f', 'c', None, None, None, None, None, None, None, None, None, None]

Note the additional 8 Nones that belong to nodes b, e, f and c.