# 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)

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

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

Next: Binary Search Tree
Previous: Depth Order Traversals: Binary Tree