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.


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

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

            if node.left:
            if node.right:

        return traversal

Complexity (using a queue)#

Average Case Worst Case
O(n) O(n)


Python for Beginners: Level Order Tree Traversal

Educative: Data Structures and Algorithms

Wikipedia: Breath-First Search

Geeks for Geeks: Level Order Binary Tree Traversal