Tree Traversal in Level Order

treeTraversalLevelOrder.py

# License: CC0 2016 Ahmad Retha
#
# Tree Traversal by order of level
# --------------------------------
#
# The goal is to get a list of elements in the order of the level they appear in the tree.
# Our tree looks like this:
#
#     a        Level 1
#    / \
#   b   c      Level 2
#  / \
# d   e        Level 3
#
# So we want to get back [a b c d e]
#

# Defining the nodes of the tree. The property 'data' holds the value of the node and
# the property 'children' the references of all of the child nodes.
class Node:
    def __init__(self, data):
        self.data = data
        self.children = []

# We create the tree now:
root = Node("a")
n2 = Node("b")
n3 = Node("c")
root.children.append(n2)
root.children.append(n3)
n4 = Node("d")
n5 = Node("e")
n2.children.append(n4)
n2.children.append(n5)

# We create two queues now. oq will contain the level-order set of nodes and
# q will hold temporary items as the tree is traversed. We initialize q with the root node.
q = [root]
oq = []

# we traverse the tree. x holds the current node which we remove from the front of the queue using pop(0).
while len(q) > 0:
    x = q.pop(0)
    oq.append(x)
    for child in x.children:
        q.append(child)

# To understand what is going on, we just follow what is in q in every loop:
# 1: [root]
# 2: [b, c]
# 3: [c, d, e]
# 4: [d, e]
# 5: [e]

# Now we output what was in oq: ['a', 'b', 'c', 'd', 'e']
print [node.data for node in oq]