</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

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.

BFS level batching decision: record last node for right view, reverse rows for zigzag, column index for vertical order

Fun fact: Binary Tree Vertical Order Traversal is a small layout problem. Assign the root column 0, a left child col - 1 and a right child col + 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:

Vertical order columns for tree 3,9,20,15,7 with column buckets

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

  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.

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.