The Idea — Level by Level
DFS dives. It picks a child, recurses all the way down, then unwinds. By the time DFS visits the root's second child, it has already visited every descendant of the first.
BFS does the opposite: it visits every node at depth 1 before touching any node at depth 2, every node at depth 2 before any at depth 3, and so on. It sweeps the tree horizontally, one level at a time.
That output — [1, 2, 3, 4, 5, 6, 7] — is exactly the tree printed row by row, left to right. BFS on a binary tree is also called level-order traversal, and the two terms mean the same thing.
Why a Queue?
DFS uses recursion (which is just a stack under the hood). Recursion goes deep — it can't help going deep, because each call dives into the next.
For BFS we need to delay going deep. When we discover a node's children, we don't want to visit them yet — we want to finish the current level first. So we need a place to park them temporarily.
The right structure is a queue (FIFO — first in, first out):
- We pull from the front to decide what to visit next.
- We add newly-discovered children to the back.
Because the queue is FIFO, anything added to the back waits behind every node that was already there. The current level always finishes before the next level starts. That's the magic — the queue's ordering rule does the level separation for us automatically.
A stack would do the opposite: newly-added children would be visited before the existing nodes, immediately taking us deep. That's literally DFS.
The Algorithm
- Initialise a queue containing just the root.
- While the queue is not empty:
- Pop the node at the front.
- Visit it (record its value, print it — whatever the problem asks).
- Enqueue its non-null children (left, then right).
That's the whole thing. Three steps inside one loop.
collections.deque is Python's double-ended queue — popleft() is O(1), which is what we need. A plain list would force O(N) pops from the front and quietly turn the algorithm quadratic.
Trace Through a Tree
Let's run BFS on the 7-node tree above and watch the queue evolve at every step.
| Step | Queue (front → back) | Action | Visit order so far |
|---|---|---|---|
| 0 | [1] | start, root enqueued | [] |
| 1 | [2, 3] | pop 1, enqueue 2, 3 | [1] |
| 2 | [3, 4, 5] | pop 2, enqueue 4, 5 | [1, 2] |
| 3 | [4, 5, 6, 7] | pop 3, enqueue 6, 7 | [1, 2, 3] |
| 4 | [5, 6, 7] | pop 4, no children | [1, 2, 3, 4] |
| 5 | [6, 7] | pop 5, no children | [1, 2, 3, 4, 5] |
| 6 | [7] | pop 6, no children | [1, 2, 3, 4, 5, 6] |
| 7 | [] | pop 7, queue empty — done | [1, 2, 3, 4, 5, 6, 7] |
Look at the queue at each step — at any moment it holds at most one full level. By the time we pop the last node of level 1 (node 3), the queue already contains the entire level 2 ([4, 5, 6, 7]). That's the level-by-level invariant in action.
Variant — Level-by-Level Grouping
A common extension: instead of a flat list [1, 2, 3, 4, 5, 6, 7], return a list per level: [[1], [2, 3], [4, 5, 6, 7]]. This is the classic LeetCode "Binary Tree Level Order Traversal" problem.
The trick is one line: snapshot the queue's length at the start of each outer iteration. That's exactly how many nodes are at the current level — pop that many, then move on.
The inner for _ in range(level_size) loop drains exactly one level. Whatever children get enqueued during that loop belong to the next level — and they're handled in the next iteration of the outer while. Clean, no extra bookkeeping.
Try It
Watch the queue grow and shrink as BFS sweeps the tree level by level.
Where You'll See BFS Again
BFS is the right tool whenever you care about distance, levels, or "smallest number of steps". You'll meet it again in:
- Shortest path in an unweighted graph — the first time BFS reaches a node is always via the fewest edges. (Covered in the graphs phase.)
- Max depth of a binary tree — count levels by running the level-order variant and returning the number of inner lists.
- Minimum depth to a leaf — return as soon as you pop a node with no children.
- Word ladder, rotting oranges, knight on chessboard — any problem framed as "fewest steps to reach a goal" is a BFS in disguise.
If you see the words "shortest", "minimum number of moves", or "level", reach for a queue.
Complexity
- Time: O(N) — each node is enqueued once and dequeued once. Constant work per node, N nodes total.
- Space: O(W) — the queue holds at most one full level. W is the maximum width of any level in the tree.
That space bound is worth comparing against DFS:
- For a balanced tree, the bottom level holds roughly N/2 nodes — so BFS space is O(N), while DFS only needs O(log N).
- For a skewed tree, every level has just one node — so BFS space is O(1), while DFS needs O(N).
The two traversals trade off in opposite directions. DFS is cheaper on balanced trees, BFS is cheaper on skewed ones — but in the worst case, both can hit O(N) memory. Pick based on what your problem actually needs: order of visits, not memory micro-optimisation.