Binary Tree Level View

Description

Level views answer questions about a tree one row at a time. Print it level by level, zigzag between directions, show what's visible from the left or right side, or find the widest level. Breadth-first search with a queue handles all of them. Snapshot the queue's size at the start of each level, and the loop knows exactly where one level ends.

We'll go from simple to more technical:

1. The pattern: BFS with a level-size snapshot.
2. A second flavor: DFS with an explicit depth (left and right views).
3. Measuring width with position indices.
4. The bugs that blur levels together, and BFS versus DFS memory.

The approach

A recursive DFS jumps between levels all the time, so it has no natural moment when "this level is done". A breadth-first walk with a queue visits the tree level by level. The one trick: at the start of each level, the queue holds exactly that level's nodes. Read the queue's size then, and process exactly that many nodes. Their children, added along the way, wait for the next round.

The right view is 7, 9, 11, 4. Notice that 4 hangs on the left side but is still the rightmost node on its level.

Queue<TreeNode> queue = new ArrayDeque<>();
if (root != null) queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();          // exactly the nodes at the current level
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        if (i == 0)        { /* leftmost of this level - left view */ }
        if (i == size - 1) { /* rightmost of this level - right view */ }
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

from collections import deque

queue = deque([root] if root else [])
while queue:
    size = len(queue)                   # exactly the nodes at the current level
    for i in range(size):
        node = queue.popleft()
        if i == 0:
            pass                        # leftmost of this level - left view
        if i == size - 1:
            pass                        # rightmost of this level - right view
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Each question here is this loop plus one choice of what to keep per level. That's the first node, the last, the whole level (reversed every other time for zigzag), or the span of positions.

A second flavor: DFS with an explicit depth

Level questions don't strictly need a queue. A DFS can carry the current depth, and the first node it reaches at each new depth is the view from one side. It just has to visit that side's child first:

void rightView(TreeNode node, int depth, List<Integer> out) {
    if (node == null) return;
    if (depth == out.size()) out.add(node.val);   // first node reached at this depth
    rightView(node.right, depth + 1, out);          // right first, so the rightmost node wins
    rightView(node.left, depth + 1, out);
}

def right_view(node: TreeNode | None, depth: int, out: list[int]) -> None:
    if node is None:
        return
    if depth == len(out):
        out.append(node.val)                  # first node reached at this depth
    right_view(node.right, depth + 1, out)    # right first, so the rightmost node wins
    right_view(node.left, depth + 1, out)

On the tree above it also returns 7, 9, 11, 4. But DFS order isn't level order. Questions that need true top-to-bottom order, like the top and bottom views (see Binary Tree Vertical Ordering), need explicit depth tracking or BFS.

Measuring width with position indices

The maximum width counts gaps too. Number the nodes like a heap: the children of position i are 2i + 1 and 2i + 2. A level's width is its last position minus its first, plus one. In the tree above, level 2 has a gap where 3's right child would be, so its width is 4. Raw positions double every level, though, and overflow on deep trees. So the queue carries (node, position) pairs, and each node's position is reduced by its level's first position before its children's are computed. No width changes, and the numbers stay small:

long idx = entry.index - first;                 // normalized: 0 .. width - 1
if (node.left != null)  queue.offer(new Entry(node.left,  2 * idx + 1));
if (node.right != null) queue.offer(new Entry(node.right, 2 * idx + 2));

idx = index - first                             # normalized: 0 .. width - 1
if node.left:
    queue.append((node.left, 2 * idx + 1))
if node.right:
    queue.append((node.right, 2 * idx + 2))

Where you'll see it

Drawing an org chart one row at a time uses exactly this loop. So does working out how wide a layout gets at its widest row.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A level-order loop is written for (int i = 0; i < queue.size(); i++). What does it print for the tree [1, 2, 3]?

2. A right-view DFS records the first node per depth but visits the left child first. What does it return for [1, 2, 3]?

3. Why does maximum width subtract each level's first position before computing the children's positions?

Key takeaways

• Read the queue's size before each level's loop. It's the only thing that marks where a level ends.
• Level questions differ only in what they keep per level: the first node, the last, the whole level, or the span of positions.
• A DFS with an explicit depth can find the side views in O(height) space, but its order isn't level order.
• Heap-style positions measure width including gaps. Normalize them per level.