templates · Trees

Level-order traversal (tree BFS)

  • The answer is per level: each level's values, average, maximum, or last node
  • "Right side view", "zigzag", "minimum depth" — the nearest or the row matters
  • You need to handle one row of the tree completely before the next

Tree BFS (level order)

the one rule

The invariant

At the start of each while round, the queue holds exactly the nodes of one level, left to right.

write it from memory

The template

levels, top to bottom

javajava.util.*
/** Values level by level, top to bottom. */static List<List<Integer>> levelOrder(TreeNode root) {    List<List<Integer>> out = new ArrayList<>();    if (root == null) return out;    Deque<TreeNode> queue = new ArrayDeque<>();    queue.offer(root);    while (!queue.isEmpty()) {        int size = queue.size();                       // freeze: this many nodes are on this level        List<Integer> level = new ArrayList<>();        for (int i = 0; i < size; i++) {            TreeNode node = queue.poll();            level.add(node.val);            if (node.left != null) queue.offer(node.left);   // children go to the next level            if (node.right != null) queue.offer(node.right);        }        out.add(level);                                // one level is done    }    return out;}

Read queue.size() once, before the loop. That number is this level; children added during the loop belong to the next one.

fill in the blanks — only these lines change per problem

  1. line 9What you keep per level: a list, a sum for the average, a max, or the first node's index for width.
  2. line 12What you do with each node of the level.
  3. line 16What happens when a level ends: add the list, compute the average, or stop early (minimum depth).

same skeleton: right side view

javajava.util.*
/** The same skeleton: keep only the last node of each level. */static List<Integer> rightSideView(TreeNode root) {    List<Integer> out = new ArrayList<>();    if (root == null) return out;    Deque<TreeNode> queue = new ArrayDeque<>();    queue.offer(root);    while (!queue.isEmpty()) {        int size = queue.size();        for (int i = 0; i < size; i++) {            TreeNode node = queue.poll();            if (i == size - 1) out.add(node.val);      // last on this level            if (node.left != null) queue.offer(node.left);            if (node.right != null) queue.offer(node.right);        }    }    return out;}

Only the visit line changed. Chalo, try zigzag the same way: reverse every second level list.

fill in the blanks — only these lines change per problem

  1. line 11Which node of the level you keep: i == size - 1 for the right view, i == 0 for the left view.

complexity

What it costs

time O(n)
Each node enters the queue once and leaves once.
space O(w)
The queue holds at most one full level, w = the widest level. For a complete tree the last level has about n/2 nodes, so plan for O(n).

watch out

Common bugs

  • Writing for (int i = 0; i < queue.size(); i++). The size changes while you add children, so levels mix.
  • Forgetting the root == null check, then putting null in the queue.
  • Adding null children to the queue and calling .val on them later.

use it

Practise it on

learn it properly