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

Question

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

Answer 1

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

Answer 2

Разве это не будет n для дерева с n узлами?

Вы посещаете каждое дерево, не так ли? Так что я бы сказал, что это линейно.