Какой будет пространственная сложность рекурсивного обхода дерева?

Пространственная сложность рекурсивного обхода дерева

При рекурсивном обходе дерева (например, in-order, pre-order, post-order) каждый рекурсивный вызов добавляет новый фрейм в стек вызовов. Глубина стека соответствует текущей глубине рекурсии, которая равна высоте дерева. Таким образом, пространственная сложность определяется высотой дерева h.

Пример

Рассмотрим бинарное дерево поиска. При рекурсивном обходе in-order:

function inorder(node) {
  if (node === null) return;
  inorder(node.left);
  console.log(node.value);
  inorder(node.right);
}

В сбалансированном дереве высота h = log(n), поэтому сложность O(log n). В вырожденном дереве (как связанный список) h = n, сложность O(n).

Применение

Этот подход используется в алгоритмах, где требуется обход дерева без дополнительной памяти, кроме стека вызовов. Однако для больших деревьев с большой высотой рекурсия может привести к переполнению стека.

Вывод

Пространственная сложность рекурсивного обхода дерева равна O(h). Это важно учитывать при работе с глубокими или несбалансированными деревьями, где может потребоваться итеративный обход с явным стеком для контроля памяти.