Как реализовать итеративный обход через стек?

Итеративный обход через стек

Итеративный обход дерева с использованием стека — это способ симуляции рекурсивного обхода без использования системного стека вызовов. Это полезно для глубоких деревьев, где рекурсия может вызвать переполнение стека, или когда требуется явный контроль над процессом.

Как это работает

Стек хранит узлы, которые нужно обработать. В зависимости от порядка обхода (preorder, inorder, postorder) алгоритм по-разному помещает и извлекает узлы. Рассмотрим preorder (корень, левый, правый):

function preorderTraversal(root) {
  if (!root) return [];
  const stack = [root];
  const result = [];
  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return result;
}

Для inorder (левый, корень, правый) нужно сначала дойти до самого левого узла, сохраняя узлы в стеке, затем извлекать и переходить к правому поддереву:

function inorderTraversal(root) {
  const stack = [];
  const result = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    result.push(curr.val);
    curr = curr.right;
  }
  return result;
}

Применение

Итеративный обход используется в алгоритмах поиска, сериализации деревьев, компиляторах (обход AST) и в задачах, где рекурсия нежелательна. Он также помогает понять, как работает стек вызовов.

Вывод: Итеративный обход через стек — это эффективная альтернатива рекурсии для обхода деревьев, особенно при ограниченной глубине стека или необходимости явного управления.