Как реализовать обход дерева без рекурсии? Какая структура данных поможет?

Обход дерева без рекурсии можно реализовать с помощью стека — это классическая структура данных для имитации рекурсивного вызова.

Например, для обхода в глубину (DFS) — preorder, inorder или postorder — алгоритм использует стек для хранения узлов, которые нужно посетить.

Пример обхода дерева в порядке preorder без рекурсии на JavaScript:

function preorderTraversal(root) {
  if (!root) return;
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    console.log(node.value); // обработка узла
    if (node.right) stack.push(node.right); // сначала правый, чтобы левый был сверху
    if (node.left) stack.push(node.left);
  }
}

Для обхода в ширину (BFS) используется очередь вместо стека.

Таким образом, стек — ключевая структура данных для обхода дерева без рекурсии, позволяющая сохранить состояние обхода и порядок посещения узлов.