Level Order Traversal Binary Tree

Definition

Level Order traversal is a breath first transversal. The traversal starts at the root and explores all the nodes at the same depth prior to moving onto the next depth level. A queue is normally needed to capture and keep track of the child nodes encountered bu not yet explored.

A breath-first traversal works well on infinite or cyclical tree, where a depth first traversal might never return with an answer or get lost in the data structure.

Implementation

100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

def levelorder_print(self, start):
        if start is None:
            return
        queue = Queue()
        queue.enqueue(start)

        traversal = ""
        while len(queue) > 0:
            traversal += str(queue.peek()) + "-"
            node = queue.dequeue()

            if node.left:
                queue.enqueue(node.left)
            if node.right:
                queue.enqueue(node.right)

        return traversal

Complexity (using a queue)

sources:

Python for Beginners: Level Order Tree Traversal

Educative: Data Structures and Algorithms

Wikipedia: Breath-First Search

Geeks for Geeks: Level Order Binary Tree Traversal