getNodes — поиск узлов дерева по типу

Задача

Дана древовидная структура. Необходимо написать функцию getNodes(tree, type), которая возвращает все ноды в порядке следования, соответствующие переданному типу. Глубина вложенности любая.

const tree = {
    type: 'nested',
    children: [
        { type: 'added', value: 42 },
        {
            type: 'nested',
            children: [{ type: 'added', value: 43 }],
        },
        { type: 'added', value: 44 },
    ],
};

Пример

const addedItems = getNodes(tree, 'added');
 
// Результат:
// [
//   { type: 'added', value: 42 },
//   { type: 'added', value: 43 },
//   { type: 'added', value: 44 },
//   ...
// ]

Решение

Оптимальное решение

// Временная сложность: O(n), где n — общее количество узлов в дереве
// Пространственная сложность: O(n) в худшем случае
// - O(n) для result (если все узлы подходят по типу)
// - O(w) для stack, где w — максимальная ширина дерева (количество узлов на одном уровне)
// - Итого: O(n + w) ≈ O(n), так как в худшем случае w может быть близко к n
 
function getNodes(tree, type) {
    const stack = [tree];
    const result = [];
 
    while (stack.length > 0) {
        const node = stack.pop();
 
        if (node.type === type) {
            result.push(node);
        }
 
        if (node.children) {
            stack.push(...node.children);
        }
    }
 
    return result.reverse();
}

См. также

• get-nodes-squirrels
• dom-walker
• trees (паттерн)