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