BFS and Views
What is this?
A "view" of a tree is what you would see standing somewhere and looking at it: from the right, from above, row by row. None of these need a special traversal. They need one breadth-first walk that records where each node sits, and then reads that record from the angle the question asks for.
The technique that makes it painless is processing a level as a unit: capture the queue's size before the loop, and that many pops are exactly one row.
Fun fact: Binary Tree Vertical Order Traversal is a small layout problem. Assign the root column
0, a left childcol - 1and a right childcol + 1, then group by column. BFS suits it better than DFS: within a column, nodes must come out top to bottom, and a breadth-first walk gives that order for free, while a depth-first walk has to record each node's row and sort by it.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: batch the queue by level, carry whatever positional information the question needs (column index, depth, direction), and the "view" is just a projection of what one ordinary traversal already recorded.
1. The level-batching skeleton
from collections import deque
queue, result = deque([root]), []
while queue:
size = len(queue) # freeze the level boundary
level = []
for _ in range(size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level) # one complete row
Capturing size before the inner loop is what makes this work. Children pushed during the loop belong to the next level, and because the boundary was frozen, they are not consumed early. Without it, levels bleed into each other and every positional answer is wrong.
From here the three problems are one-line changes: take level[-1] for the right-side view, reverse level on alternate rounds for zigzag, and carry a column index alongside each node for vertical order.
2. Carrying position
For vertical order, the queue holds (node, column) rather than bare nodes:
Note column 0 contains two nodes from different levels, and BFS delivered them in the correct top-to-bottom order without any sorting. Track the minimum and maximum column as you go, then read the buckets in order. That avoids sorting the keys at the end.
3. When BFS is not the tool
Binary Tree Longest Consecutive Sequence is in this chapter for contrast: it asks for the longest run of consecutive values along a downward path, which is a depth-first question. Its presence is a reminder that "tree" plus "longest" does not automatically mean level-order. The shape of the answer dictates the traversal, not the shape of the data.
4. Where you'll actually meet this
- Org chart and diagram drawing. Laying out a hierarchy row by row is per-level batching, and placing boxes in columns is the vertical-order computation.
- Reachability in n steps. "What can I reach in n moves" is breadth-first expansion one level at a time, the same batching over a graph instead of a tree.
5. Problems in this chapter
Binary Tree Zigzag Level Order Traversal
Level order, alternating direction each row. Batch by level, then reverse on odd rows. Do not try to alternate the traversal itself.
Pattern: level batching + conditional reverse. Target: O(n) time, O(n) space (the output alone is O(n)).
Binary Tree Vertical Order Traversal
Group nodes by column, top to bottom and left to right. Carry a column index through the queue and bucket by it.
Pattern: BFS carrying position. Target: O(n) time, O(n) space.
Binary Tree Longest Consecutive Sequence
Longest run of consecutive increasing values along a downward path. Depth-first, passing the current run length and the expected next value down.
Pattern: DFS with inherited state. Target: O(n) time, O(h) space.
6. Common pitfalls
- Not freezing the level size. The most common BFS bug: children pushed mid-loop get consumed as part of the current level.
- Reversing the queue for zigzag. Reverse the collected row instead; reversing the traversal itself corrupts the child ordering for the next level.
- Sorting columns at the end. Track min and max column during the walk and iterate the range, which is cheaper and simpler than sorting keys.
- Using DFS for vertical order without recording depth. DFS can work (preorder visits left first and a stable sort keeps ties in order), but you must record each node's row and sort by it, which costs O(n log n) instead of O(n).
- Missing the null root. Every one of these should return an empty result, not crash.
- Counting runs that climb to a parent. The run must go parent to child, so values that look like a streak (2, 3, 4, 5) do not count if they sit in a child-to-parent chain. In the lesson's tree the longest valid run is only 2 (4 -> 5 and 8 -> 9). A run also breaks the moment the value is not exactly one greater.
7. Key takeaways
- Freeze the level size before draining it. That single line separates levels correctly.
- A view is a projection, not a new traversal. Record position, then read from the angle you need.
- BFS gives top-to-bottom ordering for free, which is why vertical order prefers it over DFS.
- Carry state in the queue. Tuples of
(node, column)or(node, depth)cost nothing and remove a post-processing sort. - The answer's shape picks the traversal. Downward-path questions are DFS even in a chapter about levels.
- Why interviewers like it: BFS is universally known, so these test the details: level boundaries, positional bookkeeping, and whether you can produce three different answers from one walk.
Order: Binary Tree Zigzag Level Order Traversal → Binary Tree Vertical Order Traversal → Binary Tree Longest Consecutive Sequence.
Right Side View, the level-order warm-up this chapter builds on, is in Coding Interview 101.
Binary Tree Longest Consecutive Sequence
Core idea: Pass the parent's value and the current run length down the recursion. A child either continues the run by being exactly one greater than its parent, or restarts it at 1. Nothing has to come back up except the best length seen.
Problem, rephrased
A game studio lays out its campaign as a skill tree: each node is a level stamped with a level number, and finishing a level unlocks the child levels beneath it. The design team wants the longest streak the layout offers, a run of levels a player can clear in strictly incrementing numeric order with no gap. You're given the root of a binary tree whose node values are the level numbers.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson