Level-Order Traversal (BFS)

Difficulty: Easy · Pattern: Tree BFS · Concept: Algorithms & Data Structures — Core Data Structures

A binary tree is just a graph where every node has at most two neighbors (left, right) and there's a single entry point (root) — everything about BFS and DFS on general graphs applies directly, just with tree-specific vocabulary. Level-order traversal visits every node top-to-bottom, left-to-right within each level — exactly what BFS naturally produces, since it explores nodes in distance-from-root order.

Your task: implement level_order(root), returning a flat list of values in level order. root may be None (an empty tree).

Implement it yourself

assert level_order(tree_a) == [1, 2, 3, 4, 5]
assert level_order(tree_b) == [1, 2]
assert level_order(tree_c) == [5]
assert level_order(None) == []

Next: Right Side View of a Binary Tree (a harder BFS variant), or continue to Validate a Binary Search Tree