Для каждой ветви дерева записать номер вложенности данной ветви

Есть дерево (вложенный объект):

const three = {
  next: [
    {
      next: null,
    },
    {
      next: null,
    },
    {
      next: null,
    },
    {
      next: [
        {
          next: null,
        },
        {
          next: null,
        },
      ],
    },
  ],
}

Необходимо записать номер вложенности данной ветви:

getNestingLevelThree(three) -->

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

Примеры:

 // Аргумент функции:
 {
  next: [
    {
      next: null,
    },
    {
      next: null,
    },
    {
      next: null,
    },
    {
      next: [
        {
          next: null,
        },
        {
          next: null,
        },
      ],
    },
  ],
}

//  Возвращаемое значение функции:
{
  valueNode: 1,
  next: [
    {
      valueNode: 2,
      next: null,
    },
    {
      valueNode: 2,
      next: null,
    },
    {
      valueNode: 2,
      next: null,
    },
    {
      valueNode: 2,
      next: [
        {
          valueNode: 3,
          next: null,
        },
        {
          valueNode: 3,
          next: null,
        },
      ],
    },
  ],
}

// Аргумент функции:
{
  next: [
    {
      next: [
        {
          next: null
        }
      ]
    }
  ]
}

// Возвращаемое значение функции:

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

P.s. результаты функции и тестовых данных сравниваются с помощью результата оборачивания объектов в JSON.stringify, поэтому соблюдение порядка полей важно.

Теория по задаче

Дерево — это структура данных, где каждый узел может иметь несколько дочерних узлов. В данном формате каждый узел имеет поле next, которое либо содержит массив дочерних узлов, либо равно null.

«Уровень вложенности» (глубина) — это номер слоя, на котором находится узел: корень считается уровнем 1, его прямые дети — уровнем 2 и так далее. Поэтому во время обхода достаточно знать текущий уровень и увеличивать его на 1 при переходе к дочернему узлу.

Рекурсия — естественный способ обхода деревьев, потому что поддерево имеет ту же структуру, что и всё дерево: «узел + его дети». Чтобы рекурсия завершилась, необходимо условие остановки (базовый случай), например: «если узел равен null» или «если next не является массивом».

Итеративный обход решает ту же задачу, но вручную хранит «что обрабатывать дальше». Для этого удобно использовать стек:

В стек кладётся корень с уровнем 1.
Из стека достаётся элемент, в него записывается valueNode.
В стек добавляются его дети с уровнем на 1 больше.

Если в данных возможны циклические ссылки (например, узел прямо или косвенно ссылается сам на себя), рекурсивный обход без защиты может уйти в бесконечный цикл. Для таких случаев необходимо добавлять структуру Set для учёта посещённых узлов и прекращать обработку повторов.

Схема и сложность

Схема уровней для примера:

root (level 1)
├─ child (level 2)
├─ child (level 2)
├─ child (level 2)
└─ child (level 2)
   ├─ grandchild (level 3)
   └─ grandchild (level 3)

Оценка сложности (для всех вариантов, если каждый узел посещается один раз):

Время: O(n), где n — количество узлов.
Память:
- Рекурсия: O(h) на глубину h (стек вызовов) + при создании нового дерева дополнительно O(n) на новые объекты.
- Итерация со стеком: O(k) на стек обхода (в худшем случае до O(n)) + при клонировании дополнительно память под копию.

Таблица выбора подхода:

Подход	Меняется исходный объект	Подходит для большой глубины	Когда выбирать
Вариант A (рекурсия + новое дерево)	Нет	Иногда нет (зависит от глубины)	Когда важна неизменность данных и глубина умеренная
Вариант B (итерация + стек)	Нет (если есть копия)	Да	Когда глубина может быть большой
Вариант C (мутация)	Да	Иногда нет (зависит от глубины)	Когда допустимо менять исходный объект и важна простота

Кратко: задача решается обходом дерева с передачей текущего уровня, который увеличивается при переходе к дочерним узлам; для простоты подходит рекурсия, для очень глубокой вложенности — итеративный обход со стеком, а для неизменности исходных данных — построение нового дерева или предварительное клонирование.