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

Временная сложность обхода дерева

Обход дерева — это процесс посещения каждого узла ровно один раз. Независимо от выбранного метода (прямой, симметричный, обратный для DFS или уровневый для BFS), каждый узел обрабатывается однократно. Это означает, что временная сложность всегда линейна относительно количества узлов.

Почему O(n)?

Алгоритм обхода выполняет константное количество операций на каждый узел: проверка, добавление в стек/очередь, вывод значения. Таким образом, общее время пропорционально числу узлов n. Например, для бинарного дерева с 1000 узлами потребуется около 1000 шагов.

Пример кода (DFS на JavaScript)

function dfs(node) {
  if (!node) return;
  console.log(node.value); // посещение узла
  dfs(node.left);
  dfs(node.right);
}
// Временная сложность: O(n), где n — количество узлов

Пример кода (BFS на JavaScript)

function bfs(root) {
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    console.log(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}
// Временная сложность: O(n)

Вывод

Обход дерева всегда имеет линейную временную сложность O(n), что делает его эффективным для обработки всех узлов. Этот подход применяется в поиске, сериализации, вычислении высоты дерева и других задачах, где требуется полный обход структуры.