BFS Level-Order Traversal

Concepts: pyBFS, pyLevelOrder, pyDeque

DFS goes deep before it goes wide. BFS goes wide before it goes deep. For trees, BFS means processing all nodes at depth 0 (root), then all nodes at depth 1, then depth 2. This is called level-order traversal. The tool that makes BFS work in Python is collections.deque. Always reach for deque, never list, because deque.popleft() is O(1) while list.pop(0) is O(n). In a big tree, that difference is catastrophic. Level-Order as a Flat List Level-Order as List of Lists (Most Commonly Asked Form) Interviewers almost always want the level-by-level version: each level as its own list. The trick is to snapshot the queue's current length at the start of each iteration. That snapshot tells you exactly how many nodes are on the current level. Process that many nodes, then move to the next level.