# Level Order Traversal: Intuition, Queue, and BFS How a queue helps us process binary trees level by level, from intuition to implementation. # Level Order Traversal: Why We Walk Trees Breadth-First When you're asked to process a tree **level by level** — floor by floor, row by row, nearest nodes first — the depth-first instinct that works for so many other tree problems stops being useful. This is where **Level Order Traversal**, powered by **Breadth-First Search (BFS)**, comes in. ## The Problem: Depth vs. Breadth Take this tree: ```text 1 / \ 2 3 / \ / \ 4 5 6 7 ``` A **depth-first** traversal would go something like `1 → 2 → 4 → 5 → 3 → 6 → 7`, diving as far down one branch as it can before backtracking. A **level-order (breadth-first)** traversal instead visits every node on a given level before moving to the next: ```text Level 0: 1 Level 1: 2 → 3 Level 2: 4 → 5 → 6 → 7 ``` ## An Analogy: The Building Cleaner Imagine a cleaner working through a multi-story building. They don't jump between floors at random — they finish the entire first floor, then move to the second, then the third. That's exactly the discipline level order traversal enforces: **finish the current level before starting the next one.** ## Why a Queue? The trick that makes this traversal work is a **queue**, because a queue is First In, First Out (FIFO) — the same order in which we discover nodes is the order in which we should process them. The algorithm, in five steps: 1. Push the root onto the queue. 2. While the queue isn't empty, record how many nodes are currently in it — that number is the size of **this** level. 3. Dequeue that many nodes, one at a time, appending each node's value to the current level's result and enqueuing its left and right children (if they exist). 4. Once you've dequeued exactly that many nodes, the level is complete — push the level's array onto the final result. 5. Repeat until the queue is empty. ## Walking Through an Example Using the same tree: ```text 1 / \ 2 3 / \ / \ 4 5 6 7 ``` | Step | Queue before | Nodes processed this level | Queue after | | --- | --- | --- | --- | | 1 | `[1]` | `1` | `[2, 3]` | | 2 | `[2, 3]` | `2 → 3` | `[4, 5, 6, 7]` | | 3 | `[4, 5, 6, 7]` | `4 → 5 → 6 → 7` | `[]` | The final result: ```text [ [1], [2, 3], [4, 5, 6, 7] ] ``` ## Why a `for` Loop Inside the `while` Loop? This is the detail that trips most people up the first time. Before processing a level, we snapshot the queue's current size: ```java int levelSize = q.size(); ``` Then we loop exactly that many times: ```java for (int i = 0; i < levelSize; i++) { // process current level } ``` Why snapshot the size instead of just looping `while (!q.isEmpty())`? Because while we process nodes on the current level, we're also **enqueuing their children** — and those children belong to the *next* level. Without capping the loop at `levelSize`, we'd start processing children before the current level was finished, and the level boundaries would collapse. By fixing `levelSize` up front, we guarantee the `for` loop touches only the nodes that existed in the queue *before* any children were added — exactly the current level, nothing more. ## The Core Pattern Once this clicks, the whole problem collapses into one chain of reasoning: ```text Level-by-level traversal ↓ BFS ↓ Queue ↓ Process queue one level at a time ↓ Store each level separately ``` Whenever a problem talks about trees in terms of: * level by level * row by row * floor by floor * nearest node/level first ...that's your signal to reach for BFS with a queue, not recursion or a stack. ## Complexity **Time — O(n).** Every node is enqueued and dequeued exactly once. **Space — O(n).** In the worst case (a wide, shallow tree), the queue can hold an entire level's worth of nodes — up to roughly `n/2` for a complete binary tree — and the result array stores all `n` node values. ## Reference Implementation **Java** ```java public List> levelOrder(TreeNode root) { List> result = new ArrayList<>(); if (root == null) return result; Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); currentLevel.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(currentLevel); } return result; } ``` **Python** ```python from collections import deque def level_order(root): result = [] if not root: return result queue = deque([root]) while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result ``` ## Where This Pattern Shows Up Again Once level order traversal is second nature, a whole family of tree problems becomes a small variation on the same skeleton: * **Zigzag level order** — alternate the direction you append values in, left-to-right then right-to-left. * **Right side view** — keep only the last node processed in each level. * **Level averages / sums** — accumulate a running total instead of a list per level. * **Minimum depth** — return as soon as you dequeue a node with no children. ## The Main Takeaway Don't memorize the code — memorize the trigger. The moment a tree problem asks you to think in terms of levels, the chain is always the same: ```text Level Order → BFS → Queue ``` Once that association is automatic, the implementation writes itself.