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 the tree problem that is secretly a layout problem. Assign the root column 0, a left child col − 1 and a right child col + 1, then group by column. That is precisely how a rendering engine positions nested boxes, and it is why BFS matters here rather than DFS: within a column, nodes must come out in top-to-bottom order, and a breadth-first walk gives that ordering for free while a depth-first walk would need an explicit sort by row.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line 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:

        3
       / \
      9  20            columns:  9 → -1,  3 → 0,  20 → +1
         / \                    15 → 0,  7 → +2
        15  7

column -1: [9]
column  0: [3, 15]     ← 3 is above 15, and BFS emitted it first
column  1: [20]
column  2: [7]

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

• UI layout engines. Assigning columns and rows to nested elements is the vertical-order computation.
• Org chart and diagram rendering. Drawing a hierarchy requires exactly per-level batching to lay out each row.
• Graph and dependency visualisation. Layered layouts (Sugiyama-style) begin by assigning nodes to levels via BFS.
• Game AI. Breadth-first expansion by depth is how "what can I reach in n moves" is answered.
• Network broadcast modelling. Hop-count analysis is level batching over a graph rather than 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(width) space.

▶ 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 — cheaper and simpler than sorting keys.
• Using DFS for vertical order without recording depth. Column order is preserved but the within-column top-to-bottom order is lost; you would have to sort by row afterwards.
• Missing the null root. Every one of these should return an empty result, not crash.
• Counting consecutive runs upward. The sequence must go parent-to-child; a run is broken the moment the value is not exactly one greater.

7. Key takeaways

1. Freeze the level size before draining it — that single line separates levels correctly.
2. A view is a projection, not a new traversal. Record position, then read from the angle you need.
3. BFS gives top-to-bottom ordering for free, which is why vertical order prefers it over DFS.
4. Carry state in the queue. Tuples of (node, column) or (node, depth) cost nothing and remove a post-processing sort.
5. The answer's shape picks the traversal. Downward-path questions are DFS even in a chapter about levels.
6. 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.