Level-order BFS

38 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Imagine standing to the right of a tree and asking which node you see on each row. The tree: 1 at the top; 2 and 3 below it; 5 under 2 on the right; 4 under 3 on the right. Row by row, the rightmost nodes are 1, then 3, then 4. By hand you would draw the tree with rows and read off the right edge. The problem for a computer is that nodes are not stored in rows. Each node only knows its children. So we must manufacture the rows ourselves.

A naive way: for every row number d, search the whole tree for nodes at depth d. For a tree of height h that visits the tree h times, so a chain of 10,000 nodes costs about 10,000 × 10,000 / 2 = 50 million visits.

Build the structure, one piece at a time

Piece one: a queue. Think of a line at a counter: you join at the back, you are served from the front. Two operations, push to the back and pop from the front.

Piece two: put the root in the queue. Then repeat: pop a node, and push its children to the back. Because children join at the back, every node of row 1 is served before any node of row 2, and so on. The queue naturally serves the tree row by row. This is breadth-first search.

Piece three, the part that makes rows visible: at the start of each round, look at how many nodes are in the queue. That number is exactly the size of the current row. Pop exactly that many, pushing their children, and you have processed one row and the queue now holds exactly the next row.

The right side view is the last node popped in each round: [1, 3, 4]. The level-order list is each round's popped nodes as a row. Zigzag reverses every other row. Level averages add each row and divide by its size.

Why it is correct

The claim to prove: when a round begins, the queue contains exactly one row, all of it and nothing else. At the start it holds only the root, row 0. Suppose at the start of some round it holds exactly row d. During the round we pop those nodes one by one and push only their children, which are exactly the nodes of row d + 1. We stop after popping the recorded count, so nothing from row d + 1 is popped early. At the end the queue holds exactly row d + 1. By this step-by-step argument it holds for every row.

Because the children of a left node are pushed before the children of a right node, each row also comes out in left-to-right order, so "last popped" really is the rightmost node.

Why it is fast

Each node is pushed once and popped once, and each push and pop takes constant time. Total: 2n queue operations, O(n). Memory is the widest row, at most about n/2 for a full bottom row.

How to recognise it in an interview

Any wording with "level", "row", "depth by depth", "left to right at each height", "the widest level", "connect each node to its neighbour on the right". Say: "I will do a BFS with a queue and read the queue size at the start of each round so I know where each level ends." Binary Tree Level Order Traversal is the direct form. Binary Tree Right Side View keeps the last node of each round. Maximum Width of Binary Tree pushes (node, position) pairs with positions 2i and 2i + 1 and takes last position minus first per row.

02The idea in one line

Process one level at a time: the queue length at loop start is the level size.

Reach for it when: Level order, zigzag, right side view, level averages, max width, connect next pointers.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Right Side View of [1,2,3,null,5,null,4]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Start with the root in the queue
2. Level 0 begins: the queue holds exactly 1 node
3. Pop the 1, push children; the last one, 1, is seen from the right
4. Level 1 begins: the queue holds exactly 2 nodes
5. Pop all 2, push children; the last one, 3, is seen from the right
6. Level 2 begins: the queue holds exactly 2 nodes
7. Pop all 2, push children; the last one, 4, is seen from the right
8. Queue empty: right side view is [1,3,4]
9. Each node enters and leaves the queue once: O(n)

04Asked at Google

10 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Trees: Recursive DFS (post-order fold), Best path through each node, Root-to-leaf path carry, Lowest common ancestor, Build from traversals, Iterative traversal with a stack, Column / coordinate traversal, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree as a graph (parent pointers), Tree DP: take or skip this node, Serialize / deserialize by BFS.