Какие бывают обходы бинарного дерева: pre-order, in-order, post-order, level-order?

Три обхода в глубину различаются моментом посещения корня: до поддеревьев (pre-order), между ними (in-order) или после (post-order); level-order — обход в ширину по уровням через очередь. Все четыре работают за O(n).

Когда какой

• Pre-order (корень, левое, правое) — копирование и сериализация дерева, префиксная запись выражения.
• In-order (левое, корень, правое) — для BST выдаёт ключи по возрастанию.
• Post-order (левое, правое, корень) — сначала дети, потом родитель: удаление дерева, подсчёт высоты и размеров поддеревьев, вычисление дерева выражения.
• Level-order — минимальная глубина, «вид справа», поуровневый вывод; память O(w), где w — максимальная ширина уровня.

Итеративный in-order

Рекурсия тратит O(h) стека, и на вырожденном дереве из 10⁵ узлов может переполнить его. Явный стек:

/** Узел: { val, left, right }, отсутствующий ребёнок — null */
function inorder(root) {
  const out = [];
  const stack = [];
  let cur = root;
  while (cur || stack.length) {
    while (cur) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    out.push(cur.val);
    cur = cur.right;
  }
  return out;
}

Обход Морриса делает in-order за O(1) дополнительной памяти, временно перенаправляя правые указатели.

Коротко для собеседования

Обходы в глубину отличаются только моментом обработки корня: in-order для BST даёт сортировку, post-order нужен, когда родителю важны результаты детей, а level-order идёт по уровням через очередь. На глубоких деревьях рекурсию заменяют явным стеком, иначе легко получить переполнение стека.