Удаление из иерархии объектов всех неактивных узлов

Условие

Задача заключается в том, чтобы из дерева объектов удалить каждый узел, у которого свойство alive установлено в false. При этом, если у узла свойство alive равно true, то ни один из его предков и потомков не должен быть удалён – всё дерево, связанное с таким узлом, сохраняется.

Требования:

• Реализовать решение двумя способами: рекурсивным и итеративным.
• Описать, в каких ситуациях предпочтительнее применять каждый из подходов.
• Кратко изложить плюсы и минусы рекурсии и итерации для данной задачи.

export class TreeNode {
    constructor(
        public id: number,
        public alive: boolean,
        public children: TreeNode[],
        public parent?: TreeNode
    ) { }
}

/* SOLUTION */
class TreeNodeItem extends TreeNode {
    constructor(
        public id: number,
        public alive: boolean,
        public children: TreeNodeItem[],
        public parent?: TreeNodeItem
    ) {
        super(id, alive, children, parent);
    }
}

export function cleanTree(rootNode: TreeNodeItem) {
    /* START SOLUTION */
}

Ответ

Сохраните живые узлы, всех их предков и всё поддерево под живым узлом. Мёртвая боковая ветка без живых потомков удаляется; для пустого результата можно вернуть null.

Под «связанным деревом» здесь понимаются именно перечисленные предки и потомки, не все соседние ветки. Ниже обе версии изменяют children исходных узлов; parent у оставшихся узлов остаётся корректным.

function cleanRecursive(node, protectedByAncestor = false) {
  const keepSubtree = protectedByAncestor || node.alive;
  node.children = node.children
    .map(child => cleanRecursive(child, keepSubtree))
    .filter(Boolean);
  return keepSubtree || node.children.length ? node : null;
}
function cleanIterative(root) {
  const stack = [[root, false, false]];
  const kept = new Set();
  while (stack.length) {
    const [node, inherited, visited] = stack.pop();
    const protect = inherited || node.alive;
    if (!visited) {
      stack.push([node, protect, true]);
      for (const child of node.children) stack.push([child, protect, false]);
    } else {
      node.children = node.children.filter(child => kept.has(child));
      if (protect || node.children.length) kept.add(node);
    }
  }
  return kept.has(root) ? root : null;
}

Предполагается конечное дерево без циклов по children; parent при обходе не используется. Обе версии линейны по числу узлов. Рекурсия компактнее, но глубокая цепочка может переполнить стек; итерация хранит обход явно в памяти. Если нужно сохранить вообще весь корень при наличии хотя бы одного живого узла, это другой, более широкий контракт.