Anshu Kumar Anshu Kumar - 19 days ago 9
Python Question

Python - level order traversal using dict vs queue

My understanding of Algo & DS is a bit novice. And I'm not sure if this is a duplicate or related question or if completely trivial. Wherever I see level order traversal or BFS being mentioned I see a queue used. I'm not able to understand the intricacies of that, in terms of space and more importantly time complexity, against my implementation using dictionary.

def getLevelElements(tree, level=0, cont={}):
"""Get mapping of level and elements in a level
:param tree: Input tree, ex.
1
2
4
5
8
9
3
6
7
10
None
:return: {0: [1], 1: [2, 3], 2: [4, 5, 6, 7], 3: [8, 9, 10]}
"""
if tree is not None:
cont.setdefault(level, []).append(tree.root)
if tree.leftChild is not None:
getLevelElements(tree.leftChild, level + 1, cont)
if tree.rightChild is not None:
getLevelElements(tree.rightChild, level + 1, cont)
return cont


def levelOrderTraversalOut(tree):
levelElementsMap = getLevelElements(tree)
out = []
for elements in levelElementsMap.values():
out += elements
return out


My requirement is to get elements of tree in a list using level order traversal.

Answer

If I understand you right, you need a BFS-order of elements of the tree. I would suggest smth like this:

def bfs(tree):
    out = []
    elements = [tree.root]
    while elements:
        elem = elements.pop(0)
        out.append(elem)
        if elem.leftChild:
            elements.append(elem.leftChild)
        if elem.rightChild:
            elements.append(elem.rightChild)
    return out