Дано дерево, необходимо найти сумму всех вершин

Дано дерево (вложенный объект), необходимо найти сумму всех вершин valueNode.

Примеры:

const tree = {
  valueNode: 3,
  next: [
    {
      valueNode: 1,
      next: null,
    },
    {
      valueNode: 3,
      next: null,
    },
    {
      valueNode: 2,
      next: null,
    },
    {
      valueNode: 2,
      next: [
        {
          valueNode: 1,
          next: null,
        },
        {
          valueNode: 5,
          next: null,
        },
      ],
    },
  ],
};

sumVertices(tree) // 17

const tree = {
  valueNode: 1,
  next: [
    {
      valueNode: 3,
      next: null
    },
    {
      valueNode: 2,
      next: null
    }
  ]
} 

sumVertices(tree) // 6

Теория и объяснение

Что такое дерево в этой задаче

Каждый узел — это объект с числом valueNode и полем next, которое либо null, либо массив дочерних узлов.
Сумма по дереву — это сумма значения текущего узла плюс суммы всех его потомков.

Упрощённая схема (для первого примера):

(3)
   /    /     \      \
 (1)  (3)     (2)     (2)
                    /    \
                  (1)    (5)

Сумма должна учитывать все числа в кружках.

Как мыслить рекурсивно

Рекурсивная идея строится на том, что “часть дерева” (поддерево) имеет тот же формат, что и всё дерево.
Определяется правило:

Если узла нет (null или undefined), сумма равна 0.
Если узел есть, сумма равна node.valueNode + сумма всех детей.

В коде часто выглядит так:

базовый случай: if (root == null) return 0;
рекурсивный шаг: суммирование детей через цикл или reduce().

Зачем здесь reduce()

reduce() превращает массив в одно значение, “накапливая” результат в аккумуляторе.
В задаче аккумулятором является сумма, которая увеличивается для каждого ребёнка.

Важный момент для начинающих: если массив детей пустой, reduce() должен иметь корректное начальное значение аккумулятора. В рекурсивном решении начальное значение задано как root.valueNode, поэтому даже при пустом списке детей возвращается значение текущего узла.

Почему итерация спасает от переполнения стека

Рекурсивный вызов функции создаёт новый кадр в стеке вызовов. Если глубина дерева слишком велика, стек заканчивается.
Итеративный обход хранит “что обработать дальше” в обычном массиве (стек/очередь), поэтому ограничение по глубине становится значительно мягче.

Корректная обработка next:null

Так как по условию next бывает null, требуется проверка перед обходом детей:

надёжно: Array.isArray(node.next)
допустимо и кратко: const children = node.next ?? []

Optional chaining ?. (например, node.next?.length) полезен, когда часть цепочки может быть null/undefined. Однако в данной задаче Array.isArray(...) даёт более строгую гарантию “это массив”, а не просто “что-то существует”.

Сложность алгоритмов (время и память)

Пусть n — количество узлов в дереве.

Время у всех решений: O(n), так как каждый узел посещается один раз.
Память:
- Рекурсивный DFS: O(h), где h — высота дерева (глубина), кадры лежат в стеке вызовов.
- Итеративный DFS: O(h) в худшем случае, элементы лежат в собственном стеке.
- BFS: O(w), где w — максимальная ширина уровня, элементы лежат в очереди.

Кратко: сумма valueNode находится простым обходом всех узлов (O(n)): рекурсивный DFS — самый наглядный, но на глубоком дереве может упасть из-за стека; итеративный DFS/BFS решает ту же задачу без рекурсии и обычно надёжнее для больших глубин.