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

Question

[dc65k]

Есть классическая задача на обход дерева. Решил её не с помощью рекурсии, а с помощью стека.
Подскажите, как решить её более оптимальным способом, используя также подход со стеком?

Дерево.

const tree = {
    v: [
        {
            v: 1,
            c: [
                {
                    v: 2
                },
                {
                    v: 3,
                    c: [
                        {
                            v: 4,
                        }
                    ]
                },
                {
                    v: 5,
                    c: [
                        {
                            v: 6,
                            c: [
                                {
                                    v: 7
                                }
                            ]
                        }
                    ]
                },
            ]
        },
        {
            v: 8,
            c: [
                {
                    v: 9
                },
                {
                    v: 10,
                    c: [
                        {
                            v: 11,
                        }
                    ]
                },
                {
                    v: 12,
                },
            ]
        }
    ],
    c: {
        v: 13,
        c: [
            {
                v: 14,
            }
        ]
    }
}

const solution = (object) => {

    let output = [];

    const stack = [object];

    while (stack.length) {
        const last = stack.pop();

        if (last && typeof last.v === 'number') {
            output.push(last.v);
        }

        if (last && Array.isArray(last.v)) {
            last.v.forEach(node => stack.push(node));
        }

        if (last && Array.isArray(last.c)) {
            last.c.forEach(node => stack.push(node));
        }

        if (last && typeof last.c === 'object') {
            [last.c].forEach(node => stack.push(node));
        }
    }

    return output.sort((a, b) => a - b);
}

console.log(solution(tree));

Answer 1

[0xD34F]

Что значит оптимизировать? Не хардкодить ключи? Уменьшить количество проверок? Всё просто: вложенные данные, а значит и необходимость что-то закинуть в стек, может случиться только при обработке объектов, так что вот это и надо проверять - что текущее значение, оно instanceof Object.

Какие значения должны попадать в массив с результатами - этот вопрос тоже можно решить в более общем виде. Пусть это будет параметр - функция, принимающая значение и возвращающая true или false.

Сортировку следует убрать. Если результаты нужны именно в отсортированном виде, то сортируйте их снаружи, нечего в одной функции решать несколько задач. Если же сортировка применяется для "исправления" результатов, то кривые они потому, что вы забыли, что данные из стека извлекаются в обратном порядке, т.е., надо изменить порядок добавления данных в стек.

Короче вот, "оптимизировано":

function getNestedData(data, test) {
  const result = [];

  for (const stack = [ data ]; stack.length;) {
    const n = stack.pop();

    if (n instanceof Object) {
      stack.push(...Object.values(n).reverse());
    }

    if (test(n)) {
      result.push(n);
    }
  }

  return result;
}


console.log(getNestedData(tree, Number.isFinite));

Answer 2

[Сергей Соколов]

судя по данным, тут не бинарное дерево, и в свойстве v всегда число ("v" for "value"),
а в свойстве c — опциональный массив дочерних элементов ("c" for "children").

Проверка if (last && Array.isArray(last.v)) { тут, видимо, лишняя.
Хотя самый первый раз как раз v это массив.. Так что нужна, если данные именно такие.

Как и if (last && typeof last.c === 'object') {, за исключением корневого свойства, где это таки объект.

По мелочи — все 4 проверки одинаково проверяют наличие last

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