Quick answer: Level-order traversal is breadth-first search that processes a tree one depth layer at a time. Use collections.deque for a FIFO queue, capture the current layer size when grouping output, and maintain a visited set when the input is a graph.
Level order traversal visits a tree one level at a time. It starts with the root, then visits all children of the root, then all nodes at the next depth, and so on. In Python, the most common implementation uses collections.deque as a queue.
This traversal is breadth-first search applied to a tree. Python’s official documentation covers deque, which supports efficient queue operations.
Use level order traversal when the depth of each node matters. It is useful for printing trees by rows, finding the minimum depth of a tree, serializing tree structures, and solving interview-style binary tree problems.
It is also useful whenever a tree must be displayed in the same shape people draw it.
The queue is what preserves the level-by-level order. Nodes enter the queue from left to right, and they leave in the same order. When you process only the queue length that existed at the start of a loop cycle, you isolate one complete level.
This traversal is usually iterative because queues handle deep trees safely. A recursive solution can group by depth, but a very deep tree may hit Python’s recursion limit. For production code, the queue-based version is usually the safer default.
Basic Level Order Traversal
This example prints each node from top to bottom and left to right.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
root = Node(1, Node(2), Node(3))
queue = deque([root])
while queue:
node = queue.popleft()
print(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
The queue stores nodes that have been discovered but not processed yet.
Children are appended after their parent is processed, so the traversal naturally moves across a level before going deeper.
This flat version is enough when you only need visit order. If the caller needs row-by-row output, collect one list per depth instead.
Return Values By Level
Often, you want a list of levels rather than a flat printout.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def level_order(root):
if root is None:
return []
levels = []
queue = deque([root])
while queue:
current = []
for _ in range(len(queue)):
node = queue.popleft()
current.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.append(current)
return levels
root = Node(1, Node(2), Node(3))
print(level_order(root))
The key trick is range(len(queue)), which captures the number of nodes currently in that level.
New children are added to the queue for the next loop cycle, not the current level list.
This is the most important detail in level grouping. The queue may grow while the inner loop runs, but the inner loop still processes only the nodes that belonged to the current level when that level started.
Handle An Empty Tree
Always decide what the function should return when the root is missing.
from collections import deque
def level_order_values(root):
if root is None:
return []
queue = deque([root])
values = []
while queue:
node = queue.popleft()
values.append(node.value)
for child in (node.left, node.right):
if child is not None:
queue.append(child)
return values
Returning an empty list is a common and easy-to-test choice.
The loop over (node.left, node.right) reduces repeated code while preserving left-to-right order.
Handling None at the top keeps the rest of the function simple. It also makes tests straightforward: an empty tree should return an empty list, while a one-node tree should return one value.
Zigzag Level Order
Zigzag traversal reverses every other level.
from collections import deque
def zigzag_level_order(root):
if root is None:
return []
queue = deque([root])
levels = []
left_to_right = True
while queue:
current = []
for _ in range(len(queue)):
node = queue.popleft()
current.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not left_to_right:
current.reverse()
levels.append(current)
left_to_right = not left_to_right
return levels
This keeps the queue logic normal and reverses only the output for selected levels.
That approach is easier to read than changing the enqueue order on every level.
Zigzag output is mainly a presentation change. The tree is still explored breadth-first; only the current level list is reversed before it is stored.
Recursive Level Grouping
A recursive helper can also group nodes by depth.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def collect_by_depth(node, depth, levels):
if node is None:
return
if depth == len(levels):
levels.append([])
levels[depth].append(node.value)
collect_by_depth(node.left, depth + 1, levels)
collect_by_depth(node.right, depth + 1, levels)
root = Node(1, Node(2), Node(3))
levels = []
collect_by_depth(root, 0, levels)
print(levels)
This is not queue-based BFS, but it produces the same level grouping for a tree.
Use the queue approach for very deep trees to avoid recursion depth limits.
The recursive method can be pleasant for small examples because the depth is passed explicitly. It is also useful when you already have recursive tree-processing code and only need to collect values by depth.
N-ary Tree Level Order
For an N-ary tree, each node can have any number of children.
from collections import deque
class TreeNode:
def __init__(self, value, children=None):
self.value = value
self.children = children or []
root = TreeNode("A", [
TreeNode("B"),
TreeNode("C", [TreeNode("D"), TreeNode("E")]),
])
queue = deque([root])
levels = []
while queue:
current = []
for _ in range(len(queue)):
node = queue.popleft()
current.append(node.value)
queue.extend(node.children)
levels.append(current)
print(levels)
The same level-counting pattern works; only the child handling changes.
For an N-ary tree, queue.extend(node.children) is cleaner than appending each child one by one. It keeps child order intact and makes the traversal logic match the shape of the data.
In short, level order traversal is BFS for trees. Use a deque, process exactly the current queue length for each level, append children for the next level, and return grouped levels when the caller needs structure instead of a flat traversal.
Use A FIFO Queue
Append child nodes to the right of a deque and remove the next node with popleft. This preserves breadth-first order without repeatedly shifting a list.
Group Nodes By Level
At the beginning of a layer, record len(queue). Process exactly that many nodes and append their children for the next layer. This makes depth grouping explicit.
Handle Empty Roots
Return an empty result for a missing root according to the API contract. Do not enqueue a sentinel unless the implementation needs one and tests cover its interaction with real values.
Separate Trees From Graphs
A tree has a unique parent path, while a graph can contain cycles and repeated edges. Use a visited set keyed by node identity or stable ID for graph traversal.
Choose The Output
Return values, nodes, or lists of levels based on the caller’s needs. Avoid mixing traversal with formatting or mutation so the algorithm can be reused.
Test Breadth And Complexity
Test empty and single-node inputs, skewed and balanced trees, duplicate values, cycles in graph mode, level boundaries, and O(V + E) traversal behavior with an efficient queue.
Use the official Python deque documentation. Related Python Pool references include collections and tests.
For related traversal work, compare deque collections, graph tests, and level output before implementing BFS.
Frequently Asked Questions
What is level-order traversal?
It visits tree nodes level by level from the root, processing all nodes at one depth before moving to the next.
Which data structure should I use?
Use collections.deque as a FIFO queue so append and popleft operations remain efficient.
How do I return values by level?
Track the queue length at the start of each layer, process exactly that many nodes, and collect their children for the next level.
Can level-order traversal handle graphs?
Yes, but graphs need a visited set to prevent cycles and repeated visits; the complexity then depends on the reachable vertices and edges.
