Как реализовать обход дерева в ширину

Что проверяют

Что вы сразу пишете обход через очередь, а не пытаетесь свести BFS к рекурсии, и понимаете, чем он отличается от DFS по памяти и по применимости.

Как отвечать

Формулировка в одну фразу: очередь FIFO, достаём узел, обрабатываем, кладём его детей в конец.

void bfs(TreeNode root) {
    if (root == null) return;
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        visit(node);
        if (node.left != null)  queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

ArrayDeque предпочтительнее LinkedList: та же семантика очереди, но без отдельного объекта-узла на каждый элемент. Ограничение одно: null в ArrayDeque класть нельзя, поэтому проверка на null стоит перед add, а не после poll.

Продолжение, которое спрашивают почти всегда, это обход по уровням. Достаточно зафиксировать размер очереди в начале итерации:

while (!queue.isEmpty()) {
    int size = queue.size();
    List<Integer> level = new ArrayList<>(size);
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        level.add(node.value);
        if (node.left != null)  queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    result.add(level);
}

Сложность. Время O(n): каждый узел попадает в очередь и покидает её ровно один раз. Память O(w), где w максимальная ширина уровня. У полного бинарного дерева последний уровень содержит около половины узлов, то есть на практике O(n). У DFS наоборот: память O(h) по высоте, зато на глубоком вырожденном дереве рекурсивный DFS падает со StackOverflowError, а BFS отрабатывает.

Дерево против графа. В дереве повторных путей нет. Для графа тот же код требует Set<Node> visited, причём узел помечается посещённым в момент постановки в очередь, а не при извлечении: иначе один и тот же узел попадёт в очередь несколько раз и на плотном графе она распухнет.

Где применяют: кратчайший путь по числу рёбер в невзвешенном графе, поиск связей на N рукопожатий, послойная сериализация дерева, обход каталогов вширь, поиск в пространстве состояний, где нужна минимальная по числу шагов цепочка.

Где спотыкаются

Пишут рекурсивный обход и называют его BFS; в графовом варианте помечают узел посещённым при извлечении из очереди, из-за чего дубли и лишняя работа.