Lesson 31 — Trees IV: BFS and levels

~25 minutes · Day 34 + Day 39 · tree BFS · Python

Tonight's interview skill is learning to read a tree one row at a time. Binary Tree Level Order Traversal asks for values grouped by depth: root first, then its children, then their children. That shape shows up whenever the question says level, row, nearest, or right side.

The invariant

A queue processes nodes in the order discovered; snapshot the queue length to process exactly one level at a time.

That one sentence is the whole pattern. Depth-first search dives down a path. Breadth-first search, usually shortened to BFS, spreads outward level by level. A queue gives BFS its order: first discovered, first processed.

Level Order Traversal: the slow way first

The slow approach is to collect depth 0, then start again from the root to collect depth 1, then start again for depth 2, and so on. That is O(n · h) time for n nodes and tree height h; in a skinny tree, h = n, so this becomes O(n²). It repeats the same walk just to know where one level ends.

The better question is: while we are already walking the tree, can we know the current level boundary? Yes: before processing a level, freeze len(queue). Those nodes are exactly the current level; children appended during the loop belong to the next level.

Queue snapshot: process only the nodes already in the queue; newly appended children form the next row.

Level Order Traversal: the queue way

Use collections.deque for the queue. It supports appending on the right and popping from the left efficiently; a normal list's pop(0) has to shift the remaining items (Python wiki: time complexity).

def level_order(root):
    if not root: return []
    ans, q = [], deque([root])        # discovered, not processed
    while q:
        level = []
        for _ in range(len(q)):       # snapshot this level only
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        ans.append(level)
    return ans

The line for _ in range(len(q)) is doing the important work. Without that snapshot, the loop would keep eating newly added children and blur all levels into one long list.

Transfer: same queue, new question

Binary Tree Right Side View: return the node values visible if you stand on the right side of the tree.

Before opening the reveal: predict the move. If level order gives you every row, which value from each row should the right-side view keep?

def right_side_view(root):
    if not root: return []
    ans, q = [], deque([root])
    while q:
        size = len(q)                 # one level's boundary
        for i in range(size):
            node = q.popleft()
            if i == size - 1: ans.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
    return ans

What the trade buys you

Here w is the widest level. The returned answer itself can hold O(n) values, but the working queue only needs the current frontier.

Practice — answer before you scroll past

level = []
while q:
    node = q.popleft()
    level.append(node.val)
    if node.left: q.append(node.left)
    if node.right: q.append(node.right)
ans.append(level)

Your move (tonight)

Solve these on LeetCode, in order, logging each in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Binary Tree Level Order Traversal — first write the queue solution from memory. Your prediction line should mention the queue-length snapshot.
2. Binary Tree Right Side View — same queue, but encode the rule: keep the last node from each level.

For the encode step, write the invariant at the top of this page in your own words. Revision day should test that sentence, not the exact code.