Level Order Traversal - Tree

Question

I need to define a function called level_order_travel which takes a tree as an output, a, and prints a list of all the nodes in the list in level order.

The following code here shows this:

def create_tree(node_list, index=1):
    if index >= len(node_list) or node_list[index] is None:
        return None
    d = node_list[index]
    l = index * 2
    r = l + 1
    tree = BinaryTree(d)
    tree.set_left(create_tree(node_list, l))
    tree.set_right(create_tree(node_list, r))
    return tree

def level_order_travel(a):
###

def test():
    list_of_leaves = [None, 10, 5, 15, None, None, 11, 22]
    my_tree = create_tree(list_of_leaves )

    print("Breadth first =", level_order_travel(my_tree))

test()

This is my BinaryTree class:

class BinaryTree:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def get_left(self):
        return self.left

    def get_right(self):
        return self.right

    def set_left(self, tree):
        self.left = tree

    def set_right(self, tree):
        self.right = tree

    def set_data(self, data):
        self.data = data

    def get_data(self):
        return self.data

    def create_string(self, spaces): 
        info = ' ' * spaces + str(self.data) 
        if self.left != None: 
            info += '\n(l)' + self.left.create_string(spaces+4) 
        if not self.right == None: 
            info += '\n(r)' + self.right.create_string(spaces+4) 
        return info       

    def __str__(self): 
        representation = self.create_string(0) 
        return representation

This is my Queue class:

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

    def peek(self):
        return self.items[self.size() - 1]

This is my attempt so far:

def level_order_travel(a):
    root = a.get_data()
    q = Queue()
    q.enqueue(root)
    list_of_leaves = []
    if root is None:
        return []
    else:
        if a.get_left() is not None:
            q.enqueue(a.get_left().get_data())
        if a.get_right() is not None:
            q.enqueue(a.get_right().get_data())
    while q.is_empty() == False:
        list_of_leaves.append(q.dequeue())
    return list_of_leaves

This should produce the following output:

[10, 5, 15, 11, 22] 

but instead it produces the following output:

[10, 5, 15]

Any help is appreciated. Thank you.

Answer 1

Modify your bfs traversal function to keep track of the visited nodes, it should work for any graph (not only the acyclic ones as trees):

def breadth_first_traversal(a):
    if a is None:
        return []
    visited = set([])
    q = Queue()
    q.enqueue(a)
    list_of_leaves = []
    while not q.is_empty():
        a = q.dequeue()
        visited.add(a)      
        child = a.get_left()
        if child is not None and not child in visited:
            q.enqueue(child)
        child = a.get_right()
        if child is not None and not child in visited:
            q.enqueue(child)
        list_of_leaves.append(a.get_data())
    return list_of_leaves

test()
# ('Breadth first =', [10, 5, 15, 11, 22])

Also, if you want to use the implementation only for trees then you can further simplify (you don't need to keep track of the visited nodes, since each node is guaranteed to be visited only once, for each node has only one parent):

def breadth_first_traversal(a): # only for trees
    if a is None:
        return []
    q = Queue()
    q.enqueue(a)
    list_of_leaves = []
    while not q.is_empty():
        a = q.dequeue()
        child = a.get_left()
        if child is not None: 
            q.enqueue(child)
        child = a.get_right()
        if child is not None: 
            q.enqueue(child)
        list_of_leaves.append(a.get_data())
    return list_of_leaves