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