Рассмотрим базовую задачу на поиск BFS: Binary Tree Level Order Traversal — на LeetCode это задача №102.

Дано бинарное дерево:
3
/ \
9 20
/ \
15 7
В представлении LeetCode оно задано как: root = [3,9,20,null,null,15,7]
Нужно выполнить обход дерева по уровням и вернуть значения каждого уровня отдельным списком: [[3], [9,20], [15,7]]
На вход приходит структура TreeNode, содержащая значение и ссылки на левого и правого потомка:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode() {}

TreeNode(int val) {
this.val = val;
}

TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
В качестве результата ожидаем:
List<List<Integer>>
Решение
1. Создадим список результатов:
List<List<Integer>> res = new ArrayList<>();
2. Проверим граничный случай — если дерево пустое, сразу возвращаем пустой результат:
if (root == null) {
return res;
}
3. Для последовательной обработки вершин нам подходит очередь. Помещаем в неё корневую вершину:
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
Подготовительные работы закончены. Теперь начинается основная логика.
4. Пока очередь не пуста, обрабатываем дерево уровень за уровнем:
while (!queue.isEmpty()) {
Но здесь есть важный момент.
В начале каждой итерации запоминаем размер очереди:
int size = queue.size();
Почему это важно?
Допустим, сейчас в очереди:
[9, 20]
Значит, текущий уровень содержит 2 вершины.
Во время их обработки мы добавим в очередь 15 и 7. Но они уже относятся к следующему уровню.
Поэтому size позволяет отделить текущий уровень от следующего.

4.1. Создаём список для значений текущего уровня:
List<Integer> level = new ArrayList<>();
4.2. Обрабатываем ровно size вершин:
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();

level.add(curr.val);

if (curr.left != null) {
queue.offer(curr.left);
}

if (curr.right != null) {
queue.offer(curr.right);
}
}
То есть при обработке: [3]
в очередь попадут: [9, 20]
На следующей итерации size = 2, поэтому обрабатываем только 9 и 20.
После этого очередь становится:
[15, 7]
И так продолжаем, пока очередь не опустеет.

5. После обработки текущего уровня добавляем его в результат:
res.add(level);
Полный код:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();

if (root == null) {
return res;
}

Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);

while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();

for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
level.add(curr.val);

if (curr.left != null) {
queue.offer(curr.left);
}

if (curr.right != null) {
queue.offer(curr.right);
}
}

res.add(level);
}

return res;
}
}
Сложность:
Время: O(n) — каждую вершину посещаем один раз.

Память: O(n) — в худшем случае очередь может содержать до n вершин.

Главная идея задачи — не просто использовать Queue, а запоминать queue.size() перед обработкой уровня. Именно это позволяет обычный BFS превратить в обход дерева по уровням.