Как реализовать обход дерева (глубину/ширину)?

Что такое обход дерева?

Обход дерева — это процесс посещения каждого узла ровно один раз. Существует два основных подхода: обход в глубину (DFS) и обход в ширину (BFS). Выбор зависит от задачи: например, для поиска элемента в глубокой иерархии удобен DFS, а для нахождения кратчайшего пути — BFS.

Обход в глубину (DFS)

DFS рекурсивно или с помощью стека идёт вглубь по каждой ветви. Для бинарного дерева есть три порядка: прямой (pre-order), симметричный (in-order) и обратный (post-order). Пример на JavaScript:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function dfsPreOrder(node) {
  if (!node) return;
  console.log(node.value);
  dfsPreOrder(node.left);
  dfsPreOrder(node.right);
}

Обход в ширину (BFS)

BFS использует очередь и обходит дерево по уровням. Это полезно для поиска кратчайшего пути или для работы с графами. Пример:

function bfs(root) {
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    console.log(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

Где применяется?

• DFS — в парсерах, сериализации, поиске в графах.
• BFS — в алгоритмах поиска кратчайшего пути, веб-сканерах, анализе социальных сетей.

Вывод: DFS проще реализовать рекурсивно и он требует меньше памяти, если дерево глубокое. BFS гарантирует нахождение кратчайшего пути в невзвешенном графе, но использует больше памяти на широких деревьях.